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.

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.

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