Coloring algorithms for K5-minor free graphs

Samir Khuller*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper we give an NC algorithm to five color K5-minor free graphs. We also give a polynomial time algorithm to obtain a four coloring for a K5-minor free graph.

Original languageEnglish (US)
Pages (from-to)203-208
Number of pages6
JournalInformation Processing Letters
Volume34
Issue number4
DOIs
StatePublished - Apr 24 1990

Keywords

  • Parallel algorithms
  • graph minor
  • planar graph coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Coloring algorithms for K<sub>5</sub>-minor free graphs'. Together they form a unique fingerprint.

Cite this