Bujtás, Csilla and Tuza, Zsolt (2016) K-3-WORM COLORINGS OF GRAPHS: LOWER CHROMATIC NUMBER AND GAPS IN THE CHROMATIC SPECTRUM. DISCUSSIONES MATHEMATICAE GRAPH THEORY, 36 (3). pp. 759-772. ISSN 1234-3099
|
Text
dmgt.1891.pdf Download (263kB) | Preview |
Abstract
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.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | hypergraphs; gap in the chromatic spectrum; Feasible set; lower chromatic number; WORM coloring |
Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 03 Jan 2017 12:45 |
Last Modified: | 03 Jan 2017 12:45 |
URI: | http://real.mtak.hu/id/eprint/44380 |
Actions (login required)
![]() |
Edit Item |