# K3-Worm Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum

Discussiones Mathematicae Graph Theory (2016)

- Volume: 36, Issue: 3, page 759-772
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topCsilla Bujtás, and Zsolt Tuza. "K3-Worm Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum." Discussiones Mathematicae Graph Theory 36.3 (2016): 759-772. <http://eudml.org/doc/285926>.

@article{CsillaBujtás2016,

abstract = {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.},

author = {Csilla Bujtás, Zsolt Tuza},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {WORM coloring; lower chromatic number; feasible set; gap in the chromatic spectrum},

language = {eng},

number = {3},

pages = {759-772},

title = {K3-Worm Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum},

url = {http://eudml.org/doc/285926},

volume = {36},

year = {2016},

}

TY - JOUR

AU - Csilla Bujtás

AU - Zsolt Tuza

TI - K3-Worm Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum

JO - Discussiones Mathematicae Graph Theory

PY - 2016

VL - 36

IS - 3

SP - 759

EP - 772

AB - 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.

LA - eng

KW - WORM coloring; lower chromatic number; feasible set; gap in the chromatic spectrum

UR - http://eudml.org/doc/285926

ER -

## References

top- [1] S. Arumugam, B.K. Jose, Cs. Bujtás and Zs. Tuza, Equality of domination and transversal numbers in hypergraphs, Discrete Appl. Math. 161 (2013) 1859-1867. doi:10.1016/j.dam.2013.02.009[WoS][Crossref] Zbl1286.05115
- [2] G. Bacsó, Cs. Bujtás, Zs. Tuza and V. Voloshin, New challenges in the theory of hypergraph coloring, in: Advances in Discrete Mathematics and Applications, Ramanujan Mathematical Society Lecture Notes Series 13 (2010) 45-57.
- [3] Cs. Bujtás, E. Sampathkumar, Zs. Tuza, Ch. Dominic and L. Pushpalatha, Vertex coloring without large polychromatic stars, Discrete Math. 312 (2012) 2102-2108. doi:10.1016/j.disc.2011.04.013[WoS][Crossref] Zbl1244.05088
- [4] Cs. Bujtás, E. Sampathkumar, Zs. Tuza, M.S. Subramanya and Ch. Dominic, 3- consecutive C-colorings of graphs, Discuss. Math. Graph Theory 30 (2010) 393-405. doi:10.7151/dmgt.1502[Crossref]
- [5] Cs. Bujtás and Zs. Tuza, Maximum number of colors: C-coloring and related problems, J. Geom. 101 (2011) 83-97. doi:10.1007/s00022-011-0082-2[Crossref]
- [6] Cs. Bujtás and Zs. Tuza, Kn-WORM colorings of graphs: Feasible sets and upper chromatic number, manuscript in preparation (2015).
- [7] Cs. Bujtás, Zs. Tuza and V.I. Voloshin, Hypergraph colouring, Chapter 11 in: L.W. Beineke and R.J. Wilson, (Eds.), Topics in Chromatic Graph Theory, Encyclopedia of Mathematics and Its Applications 156 (Cambridge University Press, 2014), 230-254.
- [8] W. Goddard, K. Wash and H. Xu, WORM colorings forbidding cycles or cliques, Congr. Numer. 219 (2014) 161-173. Zbl1312.05050
- [9] W. Goddard, K. Wash and H. Xu, WORM colorings, Discuss. Math. Graph Theory 35 (2015) 571-584. doi:10.7151/dmgt.1814[Crossref]
- [10] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley-Interscience, 1995).
- [11] A. Kündgen and R. Ramamurthi, Coloring face-hypergraphs of graphs on surfaces, J. Combin. Theory Ser. B 85 (2002) 307-337. doi:10.1006/jctb.2001.2107[Crossref] Zbl1029.05057
- [12] L. Lovász, Coverings and colorings of hypergraphs, Congr. Numer. 8 (1973) 3-12. Zbl0322.05114
- [13] D. Marx, The complexity of chromatic strength and chromatic edge strength, Comput. Complexity 14 (2006) 308-340. doi:10.1007/s00037-005-0201-2[Crossref] Zbl1103.05032
- [14] F. Maffray and M. Preissmann, On the NP-completeness of the k-colorability problem for triangle-free graphs, Discrete Math. 162 (1996) 313-317. doi:10.1016/S0012-365X(97)89267-9[Crossref] Zbl0870.05021
- [15] K. Ozeki, private communication, June 2015.
- [16] V.I. Voloshin, The mixed hypergraphs, Comput. Sci. J. Moldova 1 (1993) 45-52.
- [17] V.I. Voloshin, On the upper chromatic number of a hypergraph, Australas. J. Combin. 11 (1995) 25-45. Zbl0827.05027
- [18] V.I. Voloshin, Coloring Mixed Hypergraphs: Theory, Algorithms and Applications (Fields Institute Monographs 17, Amer. Math. Soc., 2002). Zbl1001.05003
- [19] V.I. Voloshin, Mixed hypergraph coloring web site. http://spectrum.troy.edu/voloshin/mh.html
- [20] V.I. Voloshin, private communication, November 2013.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.