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

DOI10.1016/j.tcs.2016.10.011zbMath1355.68106arXiv1407.7423OpenAlexW2542720522MaRDI QIDQ730005

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 coloringSATmonochromatic cycles

Mathematics Subject Classification ID

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

Related Items (3)

Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT ⋮ Vertex partitioning problems on graphs with bounded tree width ⋮ A tractable NP-completeness proof for the two-coloring without monochromatic cycles of fixed length

Cites Work

• Unnamed Item
• Unnamed Item
• An introduction to timetabling
• 2-list-coloring planar graphs without monochromatic triangles
• Efficient algorithms for acyclic colorings of graphs
• Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult
• Coloring Graphs Using Two Colors While Avoiding Monochromatic Cycles
• Rainbow induced subgraphs in proper vertex colorings
• A graph coloring algorithm for large scheduling problems
• The complexity of satisfiability problems
• The Collective Model of Household Consumption: A Nonparametric Characterization
• The complexity of theorem-proving procedures

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