A simple algorithm for 4-coloring 3-colorable planar graphs
type: Item
instance of: scholarly article
title: A simple algorithm for 4-coloring 3-colorable planar graphs
zbMATH Open document ID: 1209.05088
author: Ken-ichi Kawarabayashi
author: Kenta Ozeki
published in: Theoretical Computer Science
publication date: 2010-06-07T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5717744
zbMATH Keywords: 3-colorable graph
zbMATH Keywords: the four color theorem
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.02.015
OpenAlex ID: W2109639734
cites work: Every planar map is four colorable. I: Discharging
cites work: Every planar map is four colorable. II: Reducibility
cites work: New approximation algorithms for graph coloring
cites work: An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
cites work: Conditional hardness for approximate coloring
cites work: Subgraph Isomorphism in Planar Graphs and Related Problems
cites work: Zero knowledge and the chromatic number
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Efficient Planarity Testing
cites work: Approximate graph coloring by semidefinite programming
cites work: Graphs on surfaces
cites work: The four-colour theorem
cites work: Improving the performance guarantee for approximate graph coloring
DOI: 10.1016/J.TCS.2010.02.015
Recommended article: Q4457742
Recommended article: Q4228512
Recommended article: Q3677782
Recommended article: Q3737449
Recommended article: An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
Recommended article: Q3122897
Recommended article: On the Hardness of 4-Coloring a 3-Colorable Graph
Recommended article: Q3722525
Recommended article: A coloring algorithm for \(4 K_1\)-free line graphs
Recommended article: Q3785973
description: scientific article; zbMATH DE number 5717744