Re: Upper bounds for chromatic number

From: Butch Malahide (bof_at_sunflower.com)
Date: 03/20/05 

Date: 19 Mar 2005 23:09:34 -0800

> Are there any known upper bounds for the chromatic number
> of the following sets S1, S2 of undirected simple graphs?
>
> - Let c > 1 be a fixed integral constant. S1 is the set of
> graphs whose clique number is c.

When c = 2 (triangle-free graphs) the chromatic number can be
arbitrarily large. I think this is the simplest construction: For a
given positive integer n > 2, consider the graph with vertex set
{(x,y): x and y integers, 1 <= x < y <= n}; (x,y) is adjacent to (u,v)
if u = y or v = x. The chromatic number is the least k such that 2^k >=
n. This example is due to Erdos and Hajnal, if I remember right.

Relevant Pages

  • Re: Maximum split subgraph
    ... > The size of the decomposition should still be linear in the size of the ... I'm interested in doing this on some prime graphs, ... I think for graphs of bounded clique width the above procedure could be ... Chordal graphs can have unbounded clique width since every grid ...
    (comp.theory)
  • Re: Question on computational complexity
    ... set of graphs satisfying your uniformity condition. ... adapt it to encode languages over a binary alphabet and that will give ... it contains one clique of size k and in addition a clique ... is hard for the complexity class you want, ...
    (comp.theory)
  • Upper bounds for chromatic number
    ... Are there any known upper bounds for the chromatic number ... S2 of undirected simple graphs? ... graphs whose clique number is c. ... Thomas ...
    (sci.math)