On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P
type: Item
instance of: scholarly article
title: On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P
zbMATH Open document ID: 1185.68351
author: André Große
author: Jörg Rothe
author: Gerd Wechsung
published in: Information Processing Letters
publication date: 2010-01-29T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5664488
zbMATH Keywords: computational complexity
zbMATH Keywords: graph colorability
zbMATH Keywords: self-reducibility
MaRDI profile type: MaRDI publication profile
full work available at URL: j.ipl.2006.04.007
OpenAlex ID: W1983658653
cites work: Every planar map is four colorable. I: Discharging
cites work: Every planar map is four colorable. II: Reducibility
cites work: Perceptrons, PP, and the polynomial hierarchy
cites work: Probabilistic polynomial time is closed under parity reductions
cites work: Some simplified NP-complete graph problems
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY
cites work: Planar graph coloring is not self-reducible, assuming P\(\neq NP\)
cites work: On self-reducibility and weak P-selectivity
cites work: The complexity of optimization problems
cites work: On the complexity of unique solutions
cites work: Immunity and Simplicity for Exact Counting and Other Counting Classes
cites work: Exact complexity of exact-four-colorability
cites work: Complexity theory and cryptology. An introduction to cryptocomplexity.
cites work: On self-transformable combinatorial problems
cites work: Natural Self-Reducible Sets
cites work: The polynomial-time hierarchy
cites work: Q4942628
cites work: More complicated questions about maxima and minima, and some closures of NP
cites work: A decisive characterization of BPP
DOI: 10.1016/J.IPL.2006.04.007
description: scientific article; zbMATH DE number 5664488