Planar graph coloring is not self-reducible, assuming P\(\neq NP\)

DOI10.1016/0304-3975(91)90081-CzbMath0729.05019OpenAlexW2087358907MaRDI QIDQ805625

Samir Khuller, Vijay V. Vazirani

Publication date: 1991

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

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90081-c

zbMATH Keywords

NP-hardplanar graph four-coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P ⋮ Paradigms for parameterized enumeration ⋮ Some Problems on Approximate Counting in Graphs and Matroids ⋮ Randomised enumeration of small witnesses using a decision oracle ⋮ Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight

Cites Work

• Random generation of combinatorial structures from a uniform distribution
• Every planar map is four colorable. I: Discharging
• Natural Self-Reducible Sets
• `` Strong NP-Completeness Results
• The Computational Complexity of Tutte Invariants for Planar Graphs

This page was built for publication: Planar graph coloring is not self-reducible, assuming P\(\neq NP\)