K₃-WORM colorings of graphs: lower chromatic number and gaps in the chromatic spectrum

DOI10.7151/DMGT.1891MaRDI QIDQ726653zbMATH OpenOpenAlexWikidataFDO

Authors Csilla Bujtás, Zsolt Tuza

Publication date 13 July 2016

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1508.01759

zbMATH Keywords

feasible setWORM coloringgap in the chromatic spectrumlower chromatic number

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

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] who asked whether every such graph has a $K_3$-WORM coloring with two colors. In fact for every integer $kge3$ 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,dots,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 $kge2$ (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. Moreover we point out a fundamental connection with the theory of the colorings of mixed hypergraphs. We list many open problems at the end.

Recommendations

• \(F\)-WORM colorings: results for 2-connected graphs
• WORM colorings of planar graphs
• Worm colorings
• Chromatic spectrum of \(K_s\)-WORM colorings of \(K_n\)
• WORM colorings forbidding cycles or cliques

Cites work

• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 786134 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• 3-consecutive C-colorings of graphs
• 3-consecutive edge coloring of a graph
• Coloring face-hypergraphs of graphs on surfaces
• Coloring mixed hypergraphs: theory, algorithms and applications
• Equality of domination and transversal numbers in hypergraphs
• Mario Gionfriddo and mixed hypergraph coloring
• Maximum number of colors: C-coloring and related problems
• New challenges in the theory of hypergraph coloring
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• The complexity of chromatic strength and chromatic edge strength
• WORM colorings forbidding cycles or cliques
• Worm colorings

Cited in

(7)

• ℱ-WORM colorings of some 2-trees: partition vectors
• \(F\)-WORM colorings: results for 2-connected graphs
• Chromatic spectrum of \(K_s\)-WORM colorings of \(K_n\)
• Facially-constrained colorings of plane graphs: a survey
• Mixed hypergraphs and beyond
• Coloring subgraphs with restricted amounts of hues
• WORM colorings of planar graphs

This page was built for publication: \(K_3\)-WORM colorings of graphs: lower chromatic number and gaps in the chromatic spectrum

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q726653)