Planar graph coloring is not self-reducible, assuming P NP

DOI10.1016/0304-3975(91)90081-CMaRDI QIDQ805625zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P
• scientific article; zbMATH DE number 2044511
• On the Hardness of 4-Coloring a 3-Colorable Graph
• On unique graph 3-colorability and parsimonious reductions in the plane
• A simple algorithm for 4-coloring 3-colorable planar graphs

Cites work

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

Cited in

(8)

• Randomised enumeration of small witnesses using a decision oracle
• Paradigms for parameterized enumeration
• Some problems on approximate counting in graphs and matroids
• Enumerating all solutions of a Boolean CSP by non-decreasing weight
• scientific article; zbMATH DE number 2044511 (Why is no real title available?)
• On unique graph 3-colorability and parsimonious reductions in the plane
• From amortized to worst case delay in enumeration algorithms
• On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P

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

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