On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P

DOI10.1016/j.ipl.2006.04.007zbMath1185.68351OpenAlexW1983658653MaRDI QIDQ845727

Jörg Rothe, André Große, Gerd Wechsung

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.04.007

zbMATH Keywords

computational complexitygraph colorabilityself-reducibility

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Probabilistic polynomial time is closed under parity reductions
• Planar graph coloring is not self-reducible, assuming P\(\neq NP\)
• Exact complexity of exact-four-colorability
• On self-reducibility and weak P-selectivity
• The complexity of optimization problems
• More complicated questions about maxima and minima, and some closures of NP
• Some simplified NP-complete graph problems
• The polynomial-time hierarchy
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Perceptrons, PP, and the polynomial hierarchy
• Complexity theory and cryptology. An introduction to cryptocomplexity.
• On the complexity of unique solutions
• Natural Self-Reducible Sets
• On self-transformable combinatorial problems
• Computational Complexity of Probabilistic Turing Machines
• Immunity and Simplicity for Exact Counting and Other Counting Classes
• A decisive characterization of BPP
• THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY

This page was built for publication: On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P