05868812

j

05868812 Aravind, N.R. Subramanian, C.R. Bounds on vertex colorings with restrictions on the union of color classes. J. Graph Theory 66, No. 3, 213-234 (2011). 2011 John Wiley \& Sons, New York, NY EN vertex coloring proper coloring forbidden subgraphs acyclic colorings bounded tree width

doi:10.1002/jgt.20501

The authors consider proper vertex colorings of simple and undirected graphs. Given a positive integer $j$ and a family ${\Cal F}$ of connected graphs, then the proper vertex colorings are required to have the following property: the union of any $j$ colour classes induces a subgraph which does not contain a copy of any member of ${\Cal F}$. This generalizes some well-known types of colorings as acyclic colorings or star colorings etc. For this type of colouring an upper bound on the minimum number of colors is obtained. For the case $j=2$, there ist also obtained a lower bound on the minimum number of colors of such colorings needed in the worst case. As special cases, 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 tree-width are considered. Ulrike Baumann (Dresden)