A tractable NP-completeness proof for the two-coloring without monochromatic cycles of fixed length

DOI10.1016/J.TCS.2017.02.005zbMATH Open1369.68246OpenAlexW2588373402MaRDI QIDQ528481FDOQ528481

Authors: Ya. N. Shitov 

Publication date: 12 May 2017

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.02.005

Recommendations

• Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• On the complexity of \(k\)-rainbow cycle colouring problems
• Coloring edges and vertices of graphs without short or long cycles
• The complexity for partitioning graphs by monochromatic trees, cycles and paths

zbMATH Keywords

graph coloringfixed-parameter tractability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• The complexity of satisfiability problems
• Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete

Cited In (4)

• Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete
• On the complexity of detecting \(k\)-length negative cost cycles
• Perspectives on CUR decompositions
• Title not available (Why is that?)

This page was built for publication: A tractable NP-completeness proof for the two-coloring without monochromatic cycles of fixed length

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