Hard coloring problems in low degree planar bipartite graphs

Chlebík, Miroslav and Chlebíková, Janka (2006) Hard coloring problems in low degree planar bipartite graphs. Discrete Applied Mathematics, 154 (14). pp. 1960-1965. ISSN 0166-218X

Full text not available from this repository.


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.

Item Type: Article
Schools and Departments: School of Mathematical and Physical Sciences > Mathematics
Depositing User: Miroslav Chlebik
Date Deposited: 06 Feb 2012 19:49
Last Modified: 04 Apr 2012 10:48
URI: http://sro.sussex.ac.uk/id/eprint/22356
📧 Request an update