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

DOI10.7151/DMGT.1891zbMATH Open1339.05116arXiv1508.01759OpenAlexW2963456061WikidataQ59072402 ScholiaQ59072402MaRDI QIDQ726653FDOQ726653

Authors: Csilla Bujtás, Zsolt Tuza 

Publication date: 13 July 2016

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

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.

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

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

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)

Cites Work

• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• 3-consecutive C-colorings of graphs
• Title not available (Why is that?)
• 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
• Worm colorings
• WORM colorings forbidding cycles or cliques
• 3-consecutive edge coloring of a graph
• Coloring face-hypergraphs of graphs on surfaces
• New challenges in the theory of hypergraph coloring
• The complexity of chromatic strength and chromatic edge strength

Cited In (7)

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