K3K_3-WORM colorings of graphs: Lower chromatic number and gaps in the chromatic spectrum

preprint2015arXivOpen access

Abstract

A K3K_3-WORM coloring of a graph GG is an assignment of colors to the vertices in such a way that the vertices of each K3K_3-subgraph of GG get precisely two colors. We study graphs GG which admit at least one such coloring. We disprove a conjecture of Goddard et al. [Congr. Numer., 219 (2014) 161--173] who asked whether every such graph has a K3K_3-WORM coloring with two colors. In fact for every integer k≥3k\ge 3 there exists a K3K_3-WORM colorable graph in which the minimum number of colors is exactly kk. There also exist K3K_3-WORM colorable graphs which have a K3K_3-WORM coloring with two colors and also with kk colors but no coloring with any of 3,…,k−13,\dots,k-1 colors. We also prove that it is NP-hard to determine the minimum number of colors and NP-complete to decide kk-colorability for every k≥2k \ge 2 (and remains intractable even for graphs of maximum degree 9 if k=3k=3). On the other hand, we prove positive results for dd-degenerate graphs with small dd, also including planar graphs. Moreover we point out a fundamental connection with the theory of the colorings of mixed hypergraphs. We list many open problems at the end.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.