Algorithmic complexity of list colorings |
| |
Authors: | Jan Kratochvíl Zsolt Tuza |
| |
Institution: | a Charles University, Sokolovska 83, 186 00 Prague 8, Czech Republic b Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 13-17, H-1111 Budapest, Hungary |
| |
Abstract: | Given a graph G = (V,E) and a finite set L(v) at each vertex v ε V, the List Coloring problem asks whether there exists a function f:V → vεVL(V) such that (i) f(v)εL(v) for each vεV and (ii) f(u) ≠f(v) whenever u, vεV and uvεE. One of our results states that this decision problem remains NP-complete even if all of the followingconditions are met: (1) each set L(v) has at most three elements, (2) each “color” xεvεVL(v) occurs in at most three sets L(v), (3) each vertex vεV has degree at most three, and (4) G is a planar graph. On the other hand, strengthening any of the assumptions (1)–(3) yields a polynomially solvable problem. The connection between List Coloring and Boolean Satisfiability is discussed, too. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|