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

被引：105

作者：

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 [J].