Given a coloring of the vertices of a graph G, we say a subgraph is rainbow if its vertices receive distinct colors. For a graph F, we define the F-upper chromatic number of G as the maximum number of colors that can be used to color the vertices of G such that there is no rainbow copy of F. We present some results on this parameter for certain graph classes. The focus is on the case that F is a star or triangle. For example, we show that the K3-upper chromatic number of any maximal outerplanar graph on n vertices is [n/2] + 1.
@article{bwmeta1.element.doi-10_7151_dmgt_1896,
author = {Wayne Goddard and Honghai Xu},
title = {Vertex Colorings without Rainbow Subgraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {989-1005},
zbl = {1350.05036},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1896}
}
Wayne Goddard; Honghai Xu. Vertex Colorings without Rainbow Subgraphs. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 989-1005. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1896/