Wszystkie pola: forbidden graph - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Worm Colorings
Autorzy:: Goddard, Wayne
Wash, Kirsti
Xu, Honghai
Powiązania:: https://bibliotekanauki.pl/articles/31339329.pdf
Data publikacji:: 2015-08-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: coloring
rainbow
monochromatic
forbidden
path
Opis:: 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.
Źródło:: Discussiones Mathematicae Graph Theory; 2015, 35, 3; 571-584
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Vertex Colorings without Rainbow Subgraphs
Autorzy:: Goddard, Wayne
Xu, Honghai
Powiązania:: https://bibliotekanauki.pl/articles/31340560.pdf
Data publikacji:: 2016-11-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: coloring
rainbow
monochromatic
forbidden
path
Opis:: 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 K₃-upper chromatic number of any maximal outerplanar graph on n vertices is [n/2] + 1.
Źródło:: Discussiones Mathematicae Graph Theory; 2016, 36, 4; 989-1005
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs
Autorzy:: Kubicka, Ewa
Kubicki, Grzegorz
McKeon, Kathleen A.
Powiązania:: https://bibliotekanauki.pl/articles/31339334.pdf
Data publikacji:: 2015-08-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: coloring
sum of colors
forbidden subgraphs
Opis:: Given graphs G and H, a vertex coloring c : V (G) →ℕ is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ (H,G), is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G, ∑(H,G), is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for ∑(H,G), discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, Gk with the property that k more colors than χ (H,G) are required to realize ∑(H,G) for H-free colorings. More complexity results and constructions of graphs requiring extra colors are given for planar and outerplanar graphs.
Źródło:: Discussiones Mathematicae Graph Theory; 2015, 35, 3; 541-555
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja