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 条

[21] Kinetics of the R + NO2 Reactions (R = i-C3H7, n-C3H7, s-C4H9 and t-C4H9) in the Temperature Range 201-489 Kt [J].

Rissanen, Matti P. ;

Arppe, Suula L. ;

Eskola, Arkke J. ;

Tammi, Matti M. ;

Timonen, Raimo S. .

JOURNAL OF PHYSICAL CHEMISTRY A, 2010, 114 (14) :4811-4817

[22] Nanosecond Breakdown Characteristics of C4F7N and Various Mixtures at Pressures Above 1 Atmosphere in Comparison with SF6 [J].

Silvestre, Luke ;

Matthies, Jakob ;

Boswell, Luke ;

Stephens, Jacob ;

Dickens, James ;

Young, Andrew ;

Neuber, Andreas .

APPLIED SCIENCES-BASEL, 2024, 14 (23)

[23] The sensitivity of C4F7N to electric field and its influence to environment-friendly insulating gas mixture C4F7N/CO2 [J].

Xiao, Song ;

Gao, Bing ;

Pang, Xuanpei ;

Zhang, Xiaoxing ;

Li, Yi ;

Tian, Shuangshuang ;

Tang, Ju ;

Luo, Yi .

JOURNAL OF PHYSICS D-APPLIED PHYSICS, 2021, 54 (05)

[24] 1,2-Dibromoethane on Cu(100): Bonding structure and transformation to C2H4 [J].

Lin, Jong-Liang ;

Lin, Yi-Shiue ;

Shih, Jain-Jung ;

Kuo, Kuan-Huang ;

Lin, Shu-Kuan ;

Wu, Tz-Shiuan ;

Shiu, Ming-Yi .

JOURNAL OF CHEMICAL PHYSICS, 2011, 135 (06)

[25] Vertex coloring (4K1, hole-twin, 5-wheel)-free graphs [J].

Dai, Yingjun ;

Foley, Angele M. ;

Hoang, Chinh T. .

THEORETICAL COMPUTER SCIENCE, 2022, 914 :14-22

[26] Mitigation of Aging Product Generation in C4F7N-Based SF6 Alternatives: A Holistic Approach [J].

Gao, Wenqiang ;

Posada, Luisa ;

Shubhashish, Shubhashish ;

Shiravand, Vahid ;

Price, Capri ;

Potyrailo, Radislav A. ;

Younsi, Karim ;

Shan, Shiyao ;

Ndiaye, Ibrahima ;

Zhou, Jierui ;

Cabrera, Charlotte ;

Zhong, Wesley ;

Suib, Steven L. ;

Cao, Yang .

ACS SUSTAINABLE CHEMISTRY & ENGINEERING, 2024, 12 (17) :6467-6472

[27] Analysis of Decomposition Products of SF6 and C4F7N under Low Energy Corona Discharge [J].

Wei, Jia ;

Park, Chanyeop ;

Uzelac, Nenad ;

Graber, Lukas .

2020 IEEE ELECTRICAL INSULATION CONFERENCE (EIC), 2020, :167-170

[28] Crystal Structure and Thermal Properties of Double-Complex Salts [M1(NH3)6][M2(C2O4)3] (M1, M2 = Co, Rh) and K3[Rh(NH3)6][Rh(C2O4)3]2•6H2O [J].

Smirnov, Pavel ;

Filatov, Evgeny ;

Kuratieva, Natalia ;

Plyusnin, Pavel ;

Korenev, Sergey .

INTERNATIONAL JOURNAL OF MOLECULAR SCIENCES, 2023, 24 (15)

[29] Copper(II) Melonates Cu3[C6N7(NCN)3]2•8H2O and [Cu(C2H8N2)2]3[C6N7(NCN)3]2•4H2O-Using the Terminal Cyano Group of the[C6N7(NCN)3]3-Ion for Complexation [J].

Clauss, Corinna ;

Schmidt, Horst ;

Schwarzer, Anke ;

Kroke, Edwin .

ZEITSCHRIFT FUR ANORGANISCHE UND ALLGEMEINE CHEMIE, 2011, 637 (14-15) :2246-2251

[30] Enhancement of hydrocarbon recovery from CH4-C2H6-C3H8 mixed hydrates via gas sweep [J].

Zhang, Guobiao ;

Sun, Youhong ;

Li, Bing ;

Shen, Yifeng ;

Qi, Yun .

FUEL, 2022, 320

← 1 2 3 4 5 →