University of Sussex
Browse

File(s) not publicly available

Hard coloring problems in low degree planar bipartite graphs

journal contribution
posted on 2023-06-08, 00:08 authored by Miroslav ChlebikMiroslav Chlebik, Janka Chlebíková
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.

History

Publication status

  • Published

Journal

Discrete Applied Mathematics

ISSN

0166-218X

Issue

14

Volume

154

Page range

1960-1965

Department affiliated with

  • Mathematics Publications

Full text available

  • No

Peer reviewed?

  • Yes

Legacy Posted Date

2012-02-06

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC