A simple algorithm for 4-coloring 3-colorable planar graphs
- 6 June 2010
- journal article
- research article
- Published by Elsevier BV in Theoretical Computer Science
- Vol. 411 (26-28), 2619-2622
- https://doi.org/10.1016/j.tcs.2010.02.015
Abstract
No abstract availableKeywords
This publication has 14 references indexed in Scilit:
- Approximation Algorithms Using Hierarchies of Semidefinite Programming RelaxationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- Conditional hardness for approximate coloringPublished by Association for Computing Machinery (ACM) ,2006
- Clique is hard to approximate within n1−εActa Mathematica, 1999
- Subgraph Isomorphism in Planar Graphs and Related ProblemsJournal of Graph Algorithms and Applications, 1999
- Zero Knowledge and the Chromatic NumberJournal of Computer and System Sciences, 1998
- An Õ(n314)-coloring algorithm for 3-colorable graphsInformation Processing Letters, 1997
- New approximation algorithms for graph coloringJournal of the ACM, 1994
- Every planar map is four colorable. Part I: DischargingIllinois Journal of Mathematics, 1977
- Every planar map is four colorable. Part II: ReducibilityIllinois Journal of Mathematics, 1977
- Efficient Planarity TestingJournal of the ACM, 1974