Deciding Relaxed Two-Colorability—A Hardness Jump

DOI10.1007/11841036_14zbMath1131.68480OpenAlexW2104805304MaRDI QIDQ5449522

Tibor Szabó, Robert Berke

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

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

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