Bounds on vertex colorings with restrictions on the union of color classes

A proper coloring of a graph is a labeled partition of its vertices into parts which are independent sets. In this paper, given a positive integer j and a family ℱ of connected graphs, we consider proper colorings in which we require that the union of any j color classes induces a subgraph which has no copy of any member of ℱ. This generalizes some well‐known types of proper colorings like acyclic colorings (where j = 2 and ℱis the collection of all even cycles) and star colorings (where j = 2 and ℱconsists of just a path on 4 vertices), etc. For this type of coloring, we obtain an upper bound of O ( d ( k − 1)/( k − j ) ) on the minimum number of colors sufficient to obtain such a coloring. Here, d refers to the maximum degree of the graph and k is the size of the smallest member of ℱ. For the case of j = 2, we also obtain lower bounds on the minimum number of colors needed in the worst case. As a corollary, we obtain bounds on the minimum number of colors sufficient to obtain proper colorings in which the union of any j color classes is a graph of bounded treewidth. In particular, using O ( d 8/7 ) colors, one can obtain a proper coloring of the vertices of a graph so that the union of any two color classes has treewidth at most 2. We also show that this bound is tight within a multiplicative factor of O ((log d ) 1/7 ). We also consider generalizations where we require simultaneously for several pairs ( j i , ℱ i ) ( i = 1, …, l ) that the union of any j i color classes has no copy of any member of ℱ i and obtain upper bounds on the corresponding chromatic numbers. © 2011 Wiley Periodicals, Inc. J Graph Theory 66: 213–234, 2011