PRECOLORING EXTENSION .1. INTERVAL-GRAPHS

被引：97

作者：

BIRO, M ^{[1
]}

HUJTER, M ^{[1
]}

TUZA, Z ^{[1
]}

机构：

[1] UNIV MISKOLC,INST MATH,H-3515 MISKOLC,HUNGARY

来源：

DISCRETE MATHEMATICS | 1992年 / 100卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(92)90646-W

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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.

引用

页码：267 / 279

页数：13

共 21 条

[11]

HUJTER M, UNPUB CLASSES PERFEC

[12]

HUJTER M, UNPUB GENERAL BOUNDS

[13]

KAHN J, IN PRESS ASYMPTOTICA

[14]

MANVEL B, 1985, GRAPHS APPL, P257

[15] EXTENDING AN EDGE-COLORING [J].

MARCOTTE, O ;

SEYMOUR, PD .

JOURNAL OF GRAPH THEORY, 1990, 14 (05) :565-573

[16]

Preparata F. P., 1985, VLSI: Algorithms and Architectures. Proceedings of the International Workshop on Parallel Computing and VLSI, P189

[17] GRAPH MINORS .2. ALGORITHMIC ASPECTS OF TREE-WIDTH [J].

ROBERTSON, N ;

SEYMOUR, PD .

JOURNAL OF ALGORITHMS, 1986, 7 (03) :309-322

[18]

SCHEFFLER P, 1990, P INT C DISCRETE MAT, P51

[19]

SCHEFFLER P, 1990, ROSTOCK MATH K, V41, P31

[20] EFFICIENT TEST FOR CIRCULAR-ARC GRAPHS [J].

TUCKER, A .

SIAM JOURNAL ON COMPUTING, 1980, 9 (01) :1-24

← 1 2 3 →