Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete

DOI10.1016/J.TCS.2016.10.011MaRDI QIDQ730005zbMATH OpenOpenAlexFDO

Authors Michał Karpiński

Publication date 23 December 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitygraph coloringmonochromatic cyclesSAT

Mathematics Subject Classification ID

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

Abstract: In this paper we study a problem of vertex two-coloring of undirected graph such that there is no monochromatic cycle of given length. We show that this problem is hard to solve. We give a proof by presenting a reduction from variation of satisfiability (SAT) problem. We show nice properties of coloring cliques with two colors which plays pivotal role in the reduction construction.

Recommendations

• A tractable NP-completeness proof for the two-coloring without monochromatic cycles of fixed length
• Coloring edges and vertices of graphs without short or long cycles
• scientific article; zbMATH DE number 4008418
• An intractability result for the vertex 3-colourability problem
• Computational complexity of (2,2) path chromatic number problem

Cites work

• 2-list-coloring planar graphs without monochromatic triangles
• A graph coloring algorithm for large scheduling problems
• An introduction to timetabling
• Coloring graphs using two colors while avoiding monochromatic cycles
• Efficient algorithms for acyclic colorings of graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1263950 (Why is no real title available?)
• Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult
• Rainbow induced subgraphs in proper vertex colorings
• The Collective Model of Household Consumption: A Nonparametric Characterization
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures

Cited in

(5)

• Vertex partitioning problems on graphs with bounded tree width
• Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT
• Coloring graphs using two colors while avoiding monochromatic cycles
• Coloring edges and vertices of graphs without short or long cycles
• A tractable NP-completeness proof for the two-coloring without monochromatic cycles of fixed length

This page was built for publication: Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete

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