Polynomial Cases for the Vertex Coloring Problem

被引：8

作者：

Karthick, T. ^{[1
]}

Maffray, Frederic ^{[2
]}

Pastor, Lucas ^{[3
]}

机构：

[1] Indian Stat Inst, Chennai Ctr, Comp Sci Unit, Chennai 600029, Tamil Nadu, India

[2] Univ Grenoble, CNRS, Lab G SCOP, Grenoble, France

[3] Univ Grenoble, Lab G SCOP, Grenoble, France

来源：

ALGORITHMICA | 2019年 / 81卷 / 03期

关键词：

Graph algorithms; Vertex coloring; Two forbidden induced subgraphs; P-5-free graphs; MODULAR DECOMPOSITION; K-COLORABILITY; GRAPHS;

D O I：

10.1007/s00453-018-0457-y

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The computational complexity of the Vertex Coloring problem is known for all hereditary classes of graphs defined by forbidding two connected five-vertex induced subgraphs, except for seven cases. We prove the polynomial-time solvability of four of these problems: for (P5, dart)-free graphs, (P5, banner)-free graphs, (P5, bull)-free graphs, and (fork, bull)-free graphs.

引用

页码：1053 / 1074

页数：22

共 34 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2] On algorithms for (P5,gem)-free graphs [J].

Bodlaender, HL ;

Brandstädt, A ;

Kratsch, D ;

Rao, M ;

Spinrad, J .

THEORETICAL COMPUTER SCIENCE, 2005, 349 (01) :2-21

[3]

Brandstadt A., 1999, Graph classes: A survey

[4] Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time [J].

Broersma, Hajo ;

Golovach, Petr A. ;

Paulusma, Daniel ;

Song, Jian .

THEORETICAL COMPUTER SCIENCE, 2012, 423 :1-10

[5]

Cameron K., ARXIV170400316

[6] Recognizing Berge graphs [J].

Chudnovsky, M ;

Cornuéjols, G ;

Liu, XM ;

Seymour, P ;

Vuskovic, K .

COMBINATORICA, 2005, 25 (02) :143-186

[7] The strong perfect graph theorem [J].

Chudnovsky, Maria ;

Robertson, Neil ;

Seymour, Paul ;

Thomas, Robin .

ANNALS OF MATHEMATICS, 2006, 164 (01) :51-229

[8] BULL-FREE BERGE GRAPHS ARE PERFECT [J].

CHVATAL, V ;

SBIHI, N .

GRAPHS AND COMBINATORICS, 1987, 3 (02) :127-139

[9] 4 CLASSES OF PERFECTLY ORDERABLE GRAPHS [J].

CHVATAL, V ;

HOANG, CT ;

MAHADEV, NVR ;

DEWERRA, D .

JOURNAL OF GRAPH THEORY, 1987, 11 (04) :481-495

[10]

Cournier A., 1994, Trees in Algebra and Programming - CAAP '94. 19th International Colloquium. Proceedings, P68, DOI 10.1007/BFb0017474

← 1 2 3 4 →