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 条

[31] Peculiarities of dehydroaromatization of CH4-C2H6 and CH4 over Mo/ZSM-5 catalysts [J].

Matus, Ekaterina V. ;

Sukhova, Olga B. ;

Ismagilov, Ilyas Z. ;

Tsikoza, Lidiya T. ;

Ismagilov, Zinfer R. .

REACTION KINETICS AND CATALYSIS LETTERS, 2009, 98 (01) :59-67

[32] Theoretical Investigation of the Mechanisms and Kinetics of the Bimolecular and Unimolecular Reactions Involving in the C4H6 Species [J].

Pham, Tien, V ;

Trang, Hoang T. Tue .

JOURNAL OF PHYSICAL CHEMISTRY A, 2021, 125 (02) :585-596

[33] Arc Erosion Behavior of Cu/Ti3SiC2 Cathodes in c-C4F8 Gas as a Substitute for SF6 Gas [J].

Liu, Zhuhan ;

Feng, Yi ;

Jiang, Ningyuan ;

Zhou, Zijue ;

Wang, Fei ;

Li, Xinchao ;

Yu, Miao .

JOURNAL OF ELECTRONIC MATERIALS, 2023, 52 (11) :7818-7832

[34] Transport and radiation properties of C4F7N-CO2 gas mixtures with added oxygen [J].

Narayanan, Venkat R. T. ;

Gnybida, Mykhailo ;

Ruempler, Christian .

JOURNAL OF PHYSICS D-APPLIED PHYSICS, 2022, 55 (29)

[35] Elastic and phonon-mode anomalies with temperature in the energetic material C6H6N4O8 [J].

Chakraborty, Soumee ;

Rajitha, R. ;

Venkatesan, V. ;

Vargeese, Anuj A. ;

Madhavan, R. Raja ;

Asuvathraman, R. ;

Ravindran, T. R. .

PHYSICAL REVIEW B, 2022, 105 (13)

[36] Determination of the Phase Behavior of (LiNH2)c(LiBH4)1-c Quaternary Hydrides through in Situ X-ray Diffraction [J].

Singer, Jonathan P. ;

Meyer, Martin S. ;

Speer, Richard M., Jr. ;

Fischer, John E. ;

Pinkerton, Frederick E. .

JOURNAL OF PHYSICAL CHEMISTRY C, 2009, 113 (43) :18927-18934

[37] Ultra-thin C3N4 nanosheets for rapid charge transfer in the core-shell heterojunction of α-sulfur@C3N4 for superior metal-free photocatalysis under visible light [J].

Dang, Xueming ;

Zhang, Xiufang ;

Zhang, Weiqiang ;

Dong, Xiaoli ;

Wang, Guowen ;

Ma, Chun ;

Zhang, Xinxin ;

Ma, Hongchao ;

Xue, Mang .

RSC ADVANCES, 2015, 5 (20) :15052-15058

[38] Theoretical Exploration of C4F7N Decompositions on GeSe Monolayers for Gas Sensing Based on DFT Method [J].

Sang, Tian-Yi ;

Sun, Hao ;

Hu, Xiqian ;

Li, Tao ;

Guo, Liang-Yan ;

Peng, Zhirong ;

Wang, Guanya ;

Zhu, Congcong ;

Zou, Simin ;

Zhang, Xiao ;

Wang, Sijie ;

Li, Wen ;

Chen, Weigen .

IEEE SENSORS JOURNAL, 2022, 22 (14) :13915-13920

[39] BALANCED TRIPARTITE ENTANGLEMENT, THE ALTERNATING GROUP A4 AND THE LIE ALGEBRA sl(3, C) ⊕ u(1) [J].

Planat, Michel ;

Levay, Peter ;

Saniga, Metod .

REPORTS ON MATHEMATICAL PHYSICS, 2011, 67 (01) :39-51

[40] Rational regulation of spatially adjacent Al4c and Al6c sites assisted Ru catalysts for low-NH3 furfural tandem reductive amination [J].

Gao, Zhexi ;

Zhao, Xinxin ;

Li, Xiumin ;

Wu, Huifang ;

Gao, Mingyu ;

Wang, Qian ;

Li, Dianqing ;

Feng, Junting .

CHEMICAL ENGINEERING SCIENCE, 2022, 258

← 1 2 3 4 5 →