Deciding Relaxed Two-Colorability—A Hardness Jump

DOI10.1007/11841036_14MaRDI QIDQ5449522zbMATH OpenOpenAlexFDO

Authors Robert Berke, Tibor Szabó

Publication date 11 March 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11841036_14

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Deciding Relaxed Two-Colourability: A Hardness Jump
• Relaxed two-coloring of cubic graphs
• Relaxed two-coloring of cubic graphs
• Colouring graphs when the number of colours is almost the maximum degree
• On \(t\)-relaxed 2-distant circular coloring of graphs

Cited in

(3)

• Deciding Relaxed Two-Colourability: A Hardness Jump
• Relaxed two-coloring of cubic graphs
• Relaxed two-coloring of cubic graphs

This page was built for publication: Deciding Relaxed Two-Colorability—A Hardness Jump

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