Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: forbidden

Sortuj według:

Ogranicz wyniki do:

Vertex Colorings without Rainbow Subgraphs

100%

Goddard W., Xu H.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 4

989-1005

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.

Worm Colorings

100%

Goddard W., Wash K., Xu H.

Discussiones Mathematicae Graph Theory

2015

tom 35

nr 3

571-584

Given a coloring of the vertices, we say subgraph H is monochromatic if every vertex of H is assigned the same color, and rainbow if no pair of vertices of H are assigned the same color. Given a graph G and a graph F, we define an F-WORM coloring of G as a coloring of the vertices of G without a rainbow or monochromatic subgraph H isomorphic to F. We present some results on this concept especially as regards to the existence, complexity, and optimization within certain graph classes. The focus is on the case that F is the path on three vertices.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Goddard W.

2 Xu H.

1 Wash K.

1 2016

1 2015

Wyniki wyszukiwania

Vertex Colorings without Rainbow Subgraphs

Worm Colorings