- Tytuł:
- K3-WORM Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum
- Autorzy:
-
Bujtás, Csilla
Tuza, Zsolt - Powiązania:
- https://bibliotekanauki.pl/articles/31340789.pdf
- Data publikacji:
- 2016-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
WORM coloring
lower chromatic number
feasible set
gap in the chromatic spectrum - Opis:
- A K3-WORM coloring of a graph G is an assignment of colors to the vertices in such a way that the vertices of each K3-subgraph of G get precisely two colors. We study graphs G which admit at least one such coloring. We disprove a conjecture of Goddard et al. [Congr. Numer. 219 (2014) 161-173] by proving that for every integer k ≥ 3 there exists a K3-WORM-colorable graph in which the minimum number of colors is exactly k. There also exist K3-WORM colorable graphs which have a K3-WORM coloring with two colors and also with k colors but no coloring with any of 3, . . ., k − 1 colors. We also prove that it is NP-hard to determine the minimum number of colors, and NP-complete to decide k-colorability for every k ≥ 2 (and remains intractable even for graphs of maximum degree 9 if k = 3). On the other hand, we prove positive results for d-degenerate graphs with small d, also including planar graphs.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2016, 36, 3; 759-772
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł