Upper bounds for chromatic number

From: Thomas Heinz (thomasheinz_at_gmx.net)
Date: 03/20/05 

Date: Sun, 20 Mar 2005 01:11:32 +0100

Hi

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.

- Let d > 0 be a fixed integral constant. S2 is the set of
   graphs such that for all G = (V, E) in S2 the following
   property holds. There exists a mapping f of each vertex
   to a d-tuple of ranges ([a_1, b_1], ..., [a_d, b_d])
   such that {u, v} in E if and only if the intersection of
   (f(u))(i) and (f(v))(i) is non-empty for all 1<=i<=d.

Remark: For the special case d = 1, S2 is the set of
         interval graphs where the chromatic number equals
         the clique number.

Thanks for your help.

Regards,

Thomas

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)
  • Re: Upper bounds for chromatic number
    ... > graphs whose clique number is c. ... I think this is the simplest construction: ... given positive integer n> 2, consider the graph with vertex set ...
    (sci.math)
  • Re: Upper bounds for chromatic number
    ... a constant depending on c. ... Since we are considering undirected graphs, ... Regards, ... Thomas ...
    (sci.math)