A coloring algorithm for 4K1-free line graphs

被引：5
作者：
Fraser, Dallas J. [1 ]
Hamel, Angele M. [1 ]
Hoang, Chinh T. [1 ]
Maffray, Frederic [2 ]
机构：
[1] Wilfrid Laurier Univ, Dept Phys & Comp Sci, Waterloo, ON, Canada
[2] Univ Grenoble Alpes, CNRS, Lab G SCOP, Grenoble, France
来源：
DISCRETE APPLIED MATHEMATICS | 2018年 / 234卷
基金：
加拿大自然科学与工程研究理事会;
关键词：
Graph coloring; Claw; K-5 \ e; Line-graph;
D O I：
10.1016/j.dam.2017.06.006
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Given a family F of graphs, let Free(F) be the class of graphs that do not contain any member of as an induced subgraph. When F is a set of four-vertex graphs the complexity of the vertex coloring problem in Free(F) is known, with three exceptions: F = {claw, 4K(1)}, = {claw, 4K(1), co-diamond}, and F = {C-4, 4K(1)}. In this paper, we study the coloring problem for Free(claw, 4K(1)). We solve the vertex coloring problem for a subclass of Free(claw, 4K(1)) which contains the class of 4K(1)-free line graphs. (C) 2017 Elsevier B.V. All rights reserved.
引用
收藏
页码：76 / 85
页数：10
相关论文
共 27 条
[1]  
[Anonymous], 1974, P 6 ACM S THEORY COM
[2]  
Beineke L.W., 1970, J. Combin. Th. Ser B, V9, P129
[3]  
Berge C., 1984, Topics on perfect graphs
[4]  
Berge C., 1961, WISS Z MARTIN LUTHER, V10, P88
[5]   GRAPHS WITH NO INDUCED C-4 AND 2K2 [J].
BLAZSIK, Z ;
HUJTER, M ;
PLUHAR, A ;
TUZA, Z .
DISCRETE MATHEMATICS, 1993, 115 (1-3) :51-55
[6]   Clique-width for 4-vertex forbidden subgraphs [J].
Brandstaedt, Andreas ;
Engelfriet, Joost ;
Le, Hoang-Oanh ;
Lozin, Vadim V. .
THEORY OF COMPUTING SYSTEMS, 2006, 39 (04) :561-590
[7]   Recognizing Berge graphs [J].
Chudnovsky, M ;
Cornuéjols, G ;
Liu, XM ;
Seymour, P ;
Vuskovic, K .
COMBINATORICA, 2005, 25 (02) :143-186
[8]   The strong perfect graph theorem [J].
Chudnovsky, Maria ;
Robertson, Neil ;
Seymour, Paul ;
Thomas, Robin .
ANNALS OF MATHEMATICS, 2006, 164 (01) :51-229
[9]   RECOGNIZING CLAW-FREE PERFECT GRAPHS [J].
CHVATAL, V ;
SBIHI, N .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1988, 44 (02) :154-176
[10]   HANDLE-REWRITING HYPERGRAPH GRAMMARS [J].
COURCELLE, B ;
ENGELFRIET, J ;
ROZENBERG, G .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1993, 46 (02) :218-270
123