Premium
Bounds on vertex colorings with restrictions on the union of color classes
Author(s) -
Aravind N. R.,
Subramanian C. R.
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20501
Subject(s) - combinatorics , mathematics , fractional coloring , discrete mathematics , greedy coloring , bounded function , complete coloring , vertex (graph theory) , treewidth , partition (number theory) , graph , graph power , pathwidth , line graph , mathematical analysis
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