Hard coloring problems in low degree planar bipartite graphs

Miroslav Chlebik, Janka Chlebikova

Research output: Contribution to journalArticlepeer-review

195 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 languageEnglish
Pages (from-to)1960-1965
JournalDiscrete Applied Mathematics
Volume154
Issue number14
DOIs
Publication statusPublished - 2006

Keywords

  • List Coloring
  • PreColoring
  • Planar graphs

Fingerprint

Dive into the research topics of 'Hard coloring problems in low degree planar bipartite graphs'. Together they form a unique fingerprint.

Cite this