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 条

[41] The thermal decomposition study of MgCl2•6H2O•1,4-C4H8O2 [J].

Jin, Miaomiao ;

Sun, Yuzhu ;

Li, Ping ;

Yu, Jianguo ;

Ulrich, Joachim .

CHEMICAL ENGINEERING RESEARCH & DESIGN, 2015, 104 :256-263

[42] Thermal studies of novel molecular perovskite energetic material (C6H14N2)[NH4(ClO4)3] [J].

Zhou, Jing ;

Ding, Li ;

Zhao, Fengqi ;

Wang, Bozhou ;

Zhang, Junlin .

CHINESE CHEMICAL LETTERS, 2020, 31 (02) :554-558

[43] Dialkyldithiocarbamate platinum(II) complexes of [Pt(S2CNR2)2] (R = iso-C3H7, iso-C4H9): Preparation, 13C CP-MAS NMR, molecular structure, supramolecular self-assembly and thermal behaviour [J].

Zaeva, Anna S. ;

Ivanov, Maxim A. ;

Gerasimenko, Andrey, V ;

Ivanov, Alexander, V ;

Antzutkin, Oleg N. .

POLYHEDRON, 2020, 175

[44] Pressure-dependent kinetics on the C4H7 potential energy surface and its effect on combustion model predictions [J].

Huang, Can ;

Yang, Bin ;

Zhang, Feng .

COMBUSTION AND FLAME, 2017, 181 :100-109

[45] Synthesis, structure analysis and thermal behavior of two new complexes: Cu(NH3)4(AFT)2 and Cu(C3H6N2H4)2(AFT)2 [J].

Ding, Zi-mei ;

Cao, Wen-li ;

Ma, Xiao ;

Hang, Xiao-jing ;

Zhang, Yu ;

Xu, Kang-zhen ;

Song, Ji-rong ;

Huang, Jie .

JOURNAL OF MOLECULAR STRUCTURE, 2019, 1175 :373-378

[46] Photocatalytic activity of the (NH4)2V6O16/g-C3N4 composite catalysts for water splitting applications [J].

Lai, Yu-Sheng ;

Dai, Yong-Ming ;

Jehng, Jih-Mirn .

CATALYSIS TODAY, 2019, 325 :41-46

[47] Mechanism and kinetics of the oxidation of 1,3-butadien-1-yl (n-C4H5): a theoretical study [J].

Porfiriev, Denis P. ;

Azyazov, Valeriy N. ;

Mebel, Alexander M. .

PHYSICAL CHEMISTRY CHEMICAL PHYSICS, 2021, 23 (15) :9198-9210

[48] Graphene oxide modified K, P co-doped g-C3N4 and CoFe2O4 composite for photocatalytic degradation of antibiotics [J].

Kumar, Rohit ;

Sudhaik, Anita ;

Sonu ;

Nguyen, Van-Huy ;

Van Le, Quyet ;

Ahamad, Tansir ;

Thakur, Sourbh ;

Kumar, Naveen ;

Hussain, Chaudhery Mustansar ;

Singh, Pardeep ;

Raizada, Pankaj .

JOURNAL OF THE TAIWAN INSTITUTE OF CHEMICAL ENGINEERS, 2023, 150

[49] Studies on deactivation behavior of SO42-/ZrO2-SiO2 catalyst derived from C2F4 and C3F6 oligomers deposition [J].

Wang, Gang ;

Li, Zengxi .

CHEMICAL ENGINEERING JOURNAL, 2022, 432

[50] Enhancement of photocatalytic activity of Bi2WO6 hybridized with graphite-like C3N4 [J].

Wang, Yajun ;

Bai, Xiaojuan ;

Pan, Chengsi ;

He, Jun ;

Zhu, Yongfa .

JOURNAL OF MATERIALS CHEMISTRY, 2012, 22 (23) :11568-11573

← 1 2 3 4 5 →