Hard coloring problems in low degree planar bipartite graphs

Miroslav Chlebik, Janka Chlebikova

Research output: Contribution to journalArticlepeer-review

225 Downloads (Pure)


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
Issue number14
Publication statusPublished - 2006


  • List Coloring
  • PreColoring
  • Planar graphs


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

Cite this