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

Abstract

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(d8/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((logd)1/7). We also consider generalizations where we require simultaneously for several pairs (ji, ℱi) (i = 1, …, l) that the union of any ji 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