Publication:845727

DOI10.1016/J.IPL.2006.04.007zbMATH Open1185.68351OpenAlexW1983658653MaRDI QIDQ845727FDOQ845727

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

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

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