Coloring algorithms for K5-minor free graphs

Samir Khuller

doi:10.1016/0020-0190(90)90161-P

Coloring algorithms for K₅-minor free graphs

Samir Khuller^*

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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

Original language	English (US)
Pages (from-to)	203-208
Number of pages	6
Journal	Information Processing Letters
Volume	34
Issue number	4
DOIs	https://doi.org/10.1016/0020-0190(90)90161-P
State	Published - 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

Access to Document

10.1016/0020-0190(90)90161-P

Cite this

@article{01477a2243f148b59d9c39615c05fc91,

title = "Coloring algorithms for K5-minor free graphs",

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.",

keywords = "Parallel algorithms, graph minor, planar graph coloring",

author = "Samir Khuller",

note = "Funding Information: * Currently supported by an IBM Graduate Fellowship. Part of this research was done while the author was supported by NSF grant DCR 85-52938 and PYI matching funds from AT&T Bell Labs.",

year = "1990",

month = apr,

day = "24",

doi = "10.1016/0020-0190(90)90161-P",

language = "English (US)",

volume = "34",

pages = "203--208",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - Coloring algorithms for K5-minor free graphs

AU - Khuller, Samir

N1 - Funding Information: * Currently supported by an IBM Graduate Fellowship. Part of this research was done while the author was supported by NSF grant DCR 85-52938 and PYI matching funds from AT&T Bell Labs.

PY - 1990/4/24

Y1 - 1990/4/24

N2 - 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.

AB - 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.

KW - Parallel algorithms

KW - graph minor

KW - planar graph coloring

UR - http://www.scopus.com/inward/record.url?scp=0025414397&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025414397&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(90)90161-P

DO - 10.1016/0020-0190(90)90161-P

M3 - Article

AN - SCOPUS:0025414397

SN - 0020-0190

VL - 34

SP - 203

EP - 208

JO - Information Processing Letters

JF - Information Processing Letters

IS - 4

ER -