K3-WORM Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 759-772
Voir la notice de l'article provenant de la source Library of Science
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.
Keywords:
WORM coloring, lower chromatic number, feasible set, gap in the chromatic spectrum
@article{DMGT_2016_36_3_a17,
author = {Bujt\'as, Csilla and Tuza, Zsolt},
title = {K\protect\textsubscript{3}-WORM {Colorings} of {Graphs:} {Lower} {Chromatic} {Number} and {Gaps} in the {Chromatic} {Spectrum}},
journal = {Discussiones Mathematicae. Graph Theory},
pages = {759--772},
publisher = {mathdoc},
volume = {36},
number = {3},
year = {2016},
language = {en},
url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a17/}
}
TY - JOUR AU - Bujtás, Csilla AU - Tuza, Zsolt TI - K3-WORM Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum JO - Discussiones Mathematicae. Graph Theory PY - 2016 SP - 759 EP - 772 VL - 36 IS - 3 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a17/ LA - en ID - DMGT_2016_36_3_a17 ER -
%0 Journal Article %A Bujtás, Csilla %A Tuza, Zsolt %T K3-WORM Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum %J Discussiones Mathematicae. Graph Theory %D 2016 %P 759-772 %V 36 %N 3 %I mathdoc %U http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a17/ %G en %F DMGT_2016_36_3_a17
Bujtás, Csilla; Tuza, Zsolt. K3-WORM Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 759-772. http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a17/