| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 421052 | Discrete Applied Mathematics | 2006 | 8 Pages |
Abstract
In the precoloring extension problem a graph is given with some of the vertices having preassigned colors and it has to be decided whether this coloring can be extended to a proper k-coloring of the graph. Answering an open question of Hujter and Tuza [Precoloring extension. III. Classes of perfect graphs, Combin. Probab. Comput. 5 (1) (1996) 35–56], we show that the precoloring extension problem is NP-complete on unit interval graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Dániel Marx,