K_3-WORM colorings of graphs: Lower chromatic number and gaps in the chromatic spectrum
Csilla Bujtás, Źsolt Tuza · Discussiones Mathematicae Graph Theory · 2016
A K 3 -WORM coloring of a graph G is an assignment of colors to the vertices in such a way that the vertices of each K 3 -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 K 3 -WORM-colorable graph in which the minimum number of colors is exactly k. There also exist K 3 -WORM colorable graphs which have a K 3 -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.