Deciding k-Colorability of P 5-Free Graphs in Polynomial Time

被引：100

作者：

Hoang, Chinh T. ^{[1
]}

Kaminski, Marcin ^{[2
]}

Lozin, Vadim ^{[3
,4
]}

Sawada, Joe ^{[5
]}

Shu, Xiao ^{[5
]}

机构：

[1] Wilfrid Laurier Univ, Waterloo, ON N2L 3C5, Canada

[2] Rutgers State Univ, RUTCOR, Piscataway, NJ 08854 USA

[3] Univ Warwick, DIMAP, Coventry CV4 7AL, W Midlands, England

[4] Univ Warwick, Math Inst, Coventry CV4 7AL, W Midlands, England

[5] Univ Guelph, Guelph, ON N1G 2W1, Canada

来源：

ALGORITHMICA | 2010年 / 57卷 / 01期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Graph coloring; Dominating clique; Polynomial-time algorithm; P(5)-free graph; FORBIDDEN SUBGRAPHS; NP-COMPLETENESS; 3-COLORABILITY;

D O I：

10.1007/s00453-008-9197-8

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The problem of computing the chromatic number of a P (5)-free graph (a graph which contains no path on 5 vertices as an induced subgraph) is known to be NP-hard. However, we show that for every fixed integer k, there exists a polynomial-time algorithm determining whether or not a P (5)-free graph admits a k-coloring, and finding one, if it does.

引用

页码：74 / 81

页数：8

共 21 条

[1] Bacso G., 1990, Period. Math. Hung., V21, P303
[2] MATRIX MULTIPLICATION VIA ARITHMETIC PROGRESSIONS
COPPERSMITH, D
WINOGRAD, S
[J]. JOURNAL OF SYMBOLIC COMPUTATION, 1990, 9 (03) : 251 - 280
[3] Coloring graphics - Foundations and applications
de Werra, D
Kobler, D
[J]. RAIRO-OPERATIONS RESEARCH, 2003, 37 (01) : 29 - 66
[4] Diestel R., 2005, GRAPH THEORY, VThird
[5] PERMUTATION GRAPHS AND TRANSITIVE GRAPHS
EVEN, S
LEMPEL, A
PNUELI, A
[J]. JOURNAL OF THE ACM, 1972, 19 (03) : 400 - &
[6] Gavril F., 1972, SIAM Journal on Computing, V1, P180, DOI 10.1137/0201013
[7] Weighted parameters in (P5,(P5)over-bar)-free graphs
Giakoumakis, V
Rusu, I
[J]. DISCRETE APPLIED MATHEMATICS, 1997, 80 (2-3) : 255 - 261
[8] Grotschel M., 1989, Ann. Discr. Math, V21, P325
[9] OPTIMIZING WEAKLY TRIANGULATED GRAPHS
HAYWARD, R
HOANG, C
MAFFRAY, F
[J]. GRAPHS AND COMBINATORICS, 1989, 5 (04) : 339 - 349
[10] HOANG CT, 2005, COLORABILITY P UNPUB

← 1 2 3 →