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 条

[1]

ARNBORG S, 1985, BIT, V25, P2, DOI 10.1007/BF01934985

[2] COMPLEXITY OF FINDING EMBEDDINGS IN A K-TREE [J].

ARNBORG, S ;

CORNEIL, DG ;

PROSKUROWSKI, A .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (02) :277-284

[3]

BIENSTOCK D, IN PRESS J COMBIN B

[4]

BISZTRAY D, 1990, COMMUNICATION

[5] LIST-COLOURINGS OF GRAPHS [J].

BOLLOBAS, B ;

HARRIS, AJ .

GRAPHS AND COMBINATORICS, 1985, 1 (02) :115-127

[6] THE COMPLEXITY OF COLORING CIRCULAR ARCS AND CHORDS [J].

GAREY, MR ;

JOHNSON, DS ;

MILLER, GL ;

PAPADIMITRIOU, CH .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1980, 1 (02) :216-227

[7]

GAREY MR, 1976, IEEE T CIRCUITS SYST, V23

[8]

Golumbic M. C., 1980, ALGORITHMIC GRAPH TH

[9]

HILTON A, 1990, GRAPH COLORINGS

[10]

HUJTER M, UNPUB GRAPH CLASSES

← 1 2 3 →