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 MathematicsISSN
0166-218XExternal DOI
Issue
14Volume
154Page range
1960-1965Department affiliated with
- Mathematics Publications
Full text available
- No
Peer reviewed?
- Yes
Legacy Posted Date
2012-02-06Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC