Hard coloring problems in low degree planar bipartite graphs

Miroslav Chlebik; Janka Chlebikova

doi:10.1016/j.dam.2006.03.014

Hard coloring problems in low degree planar bipartite graphs

Miroslav Chlebik, Janka Chlebikova

School of Computing

University of Sussex

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

409 Downloads (Pure)

Abstract

In this paper we prove that the Precoloring Extension problem on graphs of maximum degree 3 is polynomially solvable, but even its restricted version with 3 colors is NP-complete on planar bipartite graphs of maximum degree 4.

The restricted version of List Coloring, in which the union of all lists consists of 3 colors, is shown to be NP-complete on planar 3-regular bipartite graphs.

Original language	English
Pages (from-to)	1960-1965
Journal	Discrete Applied Mathematics
Volume	154
Issue number	14
DOIs	https://doi.org/10.1016/j.dam.2006.03.014
Publication status	Published - 2006

Keywords

List Coloring
PreColoring
Planar graphs

Access to Document

10.1016/j.dam.2006.03.014

1-s2.0-S0166218X06001260-main
Published under an Elsevier user licence see http://www.elsevier.com/about/open-access/open-access-policies/oa-license-policy/elsevier-user-license for more detail.
Final published version, 227 KB

Cite this

@article{ffc3c6c0fce4432d9aa8fe75f280aa65,

title = "Hard coloring problems in low degree planar bipartite graphs",

abstract = "In this paper we prove that the Precoloring Extension problem on graphs of maximum degree 3 is polynomially solvable, but even its restricted version with 3 colors is NP-complete on planar bipartite graphs of maximum degree 4. The restricted version of List Coloring, in which the union of all lists consists of 3 colors, is shown to be NP-complete on planar 3-regular bipartite graphs.",

keywords = "List Coloring, PreColoring, Planar graphs",

author = "Miroslav Chlebik and Janka Chlebikova",

note = "Published under an Elsevier user licence see http://www.elsevier.com/about/open-access/open-access-policies/oa-license-policy/elsevier-user-license for more detail.",

year = "2006",

doi = "10.1016/j.dam.2006.03.014",

language = "English",

volume = "154",

pages = "1960--1965",

journal = "Discrete Applied Mathematics",

number = "14",

}

TY - JOUR

T1 - Hard coloring problems in low degree planar bipartite graphs

AU - Chlebik, Miroslav

AU - Chlebikova, Janka

N1 - Published under an Elsevier user licence see http://www.elsevier.com/about/open-access/open-access-policies/oa-license-policy/elsevier-user-license for more detail.

PY - 2006

Y1 - 2006

N2 - In this paper we prove that the Precoloring Extension problem on graphs of maximum degree 3 is polynomially solvable, but even its restricted version with 3 colors is NP-complete on planar bipartite graphs of maximum degree 4. The restricted version of List Coloring, in which the union of all lists consists of 3 colors, is shown to be NP-complete on planar 3-regular bipartite graphs.

AB - In this paper we prove that the Precoloring Extension problem on graphs of maximum degree 3 is polynomially solvable, but even its restricted version with 3 colors is NP-complete on planar bipartite graphs of maximum degree 4. The restricted version of List Coloring, in which the union of all lists consists of 3 colors, is shown to be NP-complete on planar 3-regular bipartite graphs.

KW - List Coloring

KW - PreColoring

KW - Planar graphs

U2 - 10.1016/j.dam.2006.03.014

DO - 10.1016/j.dam.2006.03.014

M3 - Article

VL - 154

SP - 1960

EP - 1965

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 14

ER -

Hard coloring problems in low degree planar bipartite graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this