Vertex Colorings without Rainbow Subgraphs

Wayne Goddard, and Honghai Xu. "Vertex Colorings without Rainbow Subgraphs." Discussiones Mathematicae Graph Theory 36.4 (2016): 989-1005. <http://eudml.org/doc/287165>.

@article{WayneGoddard2016,
abstract = {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.},
author = {Wayne Goddard, Honghai Xu},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {coloring; rainbow; monochromatic; forbidden; path; rainbow subgraph; monochromatic subgraph; forbidden subgraph},
language = {eng},
number = {4},
pages = {989-1005},
title = {Vertex Colorings without Rainbow Subgraphs},
url = {http://eudml.org/doc/287165},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Wayne Goddard
AU - Honghai Xu
TI - Vertex Colorings without Rainbow Subgraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 4
SP - 989
EP - 1005
AB - 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.
LA - eng
KW - coloring; rainbow; monochromatic; forbidden; path; rainbow subgraph; monochromatic subgraph; forbidden subgraph
UR - http://eudml.org/doc/287165
ER -