|
|||||
|
|
Precoloring extension. I. Interval graphs |
|
| Authors: | M Bir M Hujter Zs Tuza |
| Institution: | Computer and Automation Institute, Hungarian Academy of Sciences, Budapest, Kende u 13-17, H-1111 Hungary Institute of Mathematics, University of Miskolc, Miskolc-Egyetemváros, H-3515 Hungary Computer and Automation Institute, Hungarian Academy of Sciences, Budapest, Kende u 13-17, H-1111 Hungary |
| Abstract: | This paper is the first article in a series devoted to the study of the following general problem on vertex colorings of graphs. Suppose that some vertices of a graph G are assigned to some colors. Can this ‘precoloring’ be extended to a proper coloring of G with at most k colors (for some given k)? This question was motivated by practical problems in scheduling and VLSI theory. Here we investigate its complexity status for interval graphs and for graphs with a bounded treewidth. |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ | |