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

Csilla Bujtás; Zsolt Tuza

Discussiones Mathematicae Graph Theory (2016)

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

Abstract

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

How to cite

top

Csilla 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. [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. [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. [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. [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. [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. [6] Cs. Bujtás and Zs. Tuza, Kn-WORM colorings of graphs: Feasible sets and upper chromatic number, manuscript in preparation (2015). 
  7. [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. [8] W. Goddard, K. Wash and H. Xu, WORM colorings forbidding cycles or cliques, Congr. Numer. 219 (2014) 161-173. Zbl1312.05050
  9. [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. [10] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley-Interscience, 1995). 
  11. [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. [12] L. Lovász, Coverings and colorings of hypergraphs, Congr. Numer. 8 (1973) 3-12. Zbl0322.05114
  13. [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. [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. [15] K. Ozeki, private communication, June 2015. 
  16. [16] V.I. Voloshin, The mixed hypergraphs, Comput. Sci. J. Moldova 1 (1993) 45-52. 
  17. [17] V.I. Voloshin, On the upper chromatic number of a hypergraph, Australas. J. Combin. 11 (1995) 25-45. Zbl0827.05027
  18. [18] V.I. Voloshin, Coloring Mixed Hypergraphs: Theory, Algorithms and Applications (Fields Institute Monographs 17, Amer. Math. Soc., 2002). Zbl1001.05003
  19. [19] V.I. Voloshin, Mixed hypergraph coloring web site. http://spectrum.troy.edu/voloshin/mh.html 
  20. [20] V.I. Voloshin, private communication, November 2013. 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.