On the structure and clique-width of ( 4 K 1 , C 4 , C 6 , C 7 )-free graphs

被引：1

作者：

Penev, Irena ^{[1
]}

机构：

[1] Charles Univ IUUK, Comp Sci Inst, Malostranske 25, Prague 11800, Czech Republic

来源：

JOURNAL OF GRAPH THEORY | 2022年 / 99卷 / 03期

关键词：

clique-width; even-hole-free graphs; graph algorithms; graph coloring; graph structure; HOLE-FREE GRAPHS; DECOMPOSITION; CUTSETS;

D O I：

10.1002/jgt.22749

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We give a complete structural description of ( 4 K 1 , C 4 , C 6 , C 7 )-free graphs that do not contain a simplicial vertex, and we prove that such graphs have bounded clique-width. Together with the results of Foley et al., this implies that ( 4 K 1 , C 4 , C 6 )-free graphs that do not contain a simplicial vertex have bounded clique-width. Consequently, Graph Coloring can be solved in polynomial time for ( 4 K 1 , C 4 , C 6 )-free graphs, that is, for even-hole-free graphs of stability number at most three.

引用

页码：435 / 460

页数：26

共 50 条

[1] On the clique-width of (4K1, C4, C5, C7)-free graphs
Penev, Irena
DISCRETE APPLIED MATHEMATICS, 2020, 285 : 688 - 690
[2] Coloring (4K1,C4,C6)-free graphs
Penev, Irena
DISCRETE MATHEMATICS, 2023, 346 (11)
[3] A Note on Coloring (4K1, C4, C6)-Free Graphs with a C7
Koutecky, Martin
GRAPHS AND COMBINATORICS, 2022, 38 (05)
[4] Characterizations of (4K1, C4, C5)-free graphs
Fraser, Dallas J.
Hamel, Angele M.
Hoang, Chinh T.
Holmes, Kevin
LaMantia, Tom P.
DISCRETE APPLIED MATHEMATICS, 2017, 231 : 166 - 174
[5] The optimal χ-bound for ( P7 , C4 , C5)-free graphs
Huang, Shenwei
DISCRETE MATHEMATICS, 2024, 347 (07)
[6] Linearly χ-bounding (P6, C4)-free graphs
Gaspers, Serge
Huang, Shenwei
JOURNAL OF GRAPH THEORY, 2019, 92 (03) : 322 - 342
[7] RECOGNITION OF C4-FREE AND 1/2-HYPERBOLIC GRAPHS
Coudert, David
Ducoffe, Guillaume
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2014, 28 (03) : 1601 - 1617
[8] The clique-transversal set problem in {claw, K4}-free planar graphs
Liang, Zuosong
Shan, Erfang
Kang, Liying
INFORMATION PROCESSING LETTERS, 2017, 118 : 64 - 68
[9] A Note on Coloring (4K1,C4,C6)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(4K_1, C_4, C_6)$$\end{document}-Free Graphs with a C7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C_7$$\end{document}
Martin Koutecký
Graphs and Combinatorics, 2022, 38 (5)
[10] A coloring algorithm for 4K1-free line graphs
Fraser, Dallas J.
Hamel, Angele M.
Hoang, Chinh T.
Maffray, Frederic
DISCRETE APPLIED MATHEMATICS, 2018, 234 : 76 - 85

← 1 2 3 4 5 →