Vertex Colorings without Rainbow Subgraphs

• Autorzy: Wayne Goddard , Honghai Xu
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

coloring; rainbow; monochromatic; forbidden; path

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 4
• Strony: 989-1005

Daty

wydano

2016-11-01

otrzymano

2015-07-01

poprawiono

2016-01-15

zaakceptowano

2016-01-15

online

2016-10-21

Twórcy

autor

Wayne Goddard

• Department of Mathematical Sciences Clemson University,

autor

Honghai Xu

• Department of Mathematical Sciences Clemson University,

Identyfikatory

DOI

10.7151/dmgt.1896