Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete
From MaRDI portal
Publication:730005
DOI10.1016/j.tcs.2016.10.011zbMath1355.68106arXiv1407.7423OpenAlexW2542720522MaRDI QIDQ730005
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
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