Planar graph coloring is not self-reducible, assuming P\(\neq NP\)
type: Item
instance of: scholarly article
title: Planar graph coloring is not self-reducible, assuming P\(\neq NP\)
zbMATH Open document ID: 0729.05019
DOI: 10.1016/0304-3975(91)90081-C
author: Samir Khuller
author: Vijay V. Vazirani
published in: Theoretical Computer Science
publication date: 1991-01-01T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 4204366
zbMATH Keywords: NP-hard
zbMATH Keywords: planar graph four-coloring
MaRDI profile type: Publication
cites work: Every planar map is four colorable. I: Discharging
cites work: `` Strong '' NP-Completeness Results
cites work: Random generation of combinatorial structures from a uniform distribution
cites work: Natural Self-Reducible Sets
cites work: The Computational Complexity of Tutte Invariants for Planar Graphs
full work available at URL: 0304-3975(91)90081-c
OpenAlex ID: W2087358907
description: scientific article; zbMATH DE number 4204366