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

DOI10.1016/J.TCS.2017.02.005MaRDI QIDQ528481zbMATHOpenAlexFDO

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

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)

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

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
• scientific article; zbMATH DE number 2140323 (Why is no real title available?)
• Perspectives on CUR decompositions

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)