Problem 4.3: Color-bound families of graphs


During his visit to Odense University in September 1995 András Gyárfás, Computer and Automation Institute of the Hungarian Academy of Sciences in Budapest, pointed out that Problem 4.3 has a trivial solution. In fact the solution is almost given in the comments to the problem in the book (page 81).

Complete bipartite graphs have chromatic number 2, but they may have arbitrarily high colouring number col. These graphs belong to G(T) whenever T contains a path of length 3. Hence for such a T the answer to the posed problem is NO.

In the remaining cases T is a star, and then the answer is YES. Suppose namely that G is k-chromatic without an induced K1,t. If a vertex x has degree d then the graph spanned by the neighbours of x is (k-1)-colorable with at most t-1 independent vertices., hence d is at most (t-1)(k-1). Since col(G)-1 is at most the maximum degree, it follows that (t-1)(k-1)+1 is an upper bound for col(G). This gives the existence of fT when T is a star.

If G(T) instead is defined as the smaller class of graphs not containing T as a subgraph at all, then the answer is YES for all trees T. Let T have t edges and let G be a graph not containing T as a subgraph. Then any subgraph of G has a vertex of degree at most t-1 and hence coloring number col(G) at most t (this is easy to see inductively - it is stated explicitely as Korollar 0.5.4 (Corollary 1.5.4) in [R. Diestel, Graphentheorie, Springer 1996; (English version, Graph Theory, Springer 1997)]. Then for fT(x)=x/t the chromatic number of any non-empty graph G in G(T) is at least fT(col(G)).

Hence, both when "induced" is required and "non-induced" is allowed, the answers to the posed Problem 4.3 are really trivial. We ought to have noticed this before putting the problem into the book.

August 12, 1997. B. Toft.


Back to Overview menu
Back to Graph Coloring Problems homepage

Last modified August 12, 1997 Bjarne Toft