- 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ł