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
    Rissanen, Matti P.
    Arppe, Suula L.
    Eskola, Arkke J.
    Tammi, Matti M.
    Timonen, Raimo S.
    [J]. JOURNAL OF PHYSICAL CHEMISTRY A, 2010, 114 (14) : 4811 - 4817
  • [22] The sensitivity of C4F7N to electric field and its influence to environment-friendly insulating gas mixture C4F7N/CO2
    Xiao, Song
    Gao, Bing
    Pang, Xuanpei
    Zhang, Xiaoxing
    Li, Yi
    Tian, Shuangshuang
    Tang, Ju
    Luo, Yi
    [J]. JOURNAL OF PHYSICS D-APPLIED PHYSICS, 2021, 54 (05)
  • [23] Vertex coloring (4K1, hole-twin, 5-wheel)-free graphs
    Dai, Yingjun
    Foley, Angele M.
    Hoang, Chinh T.
    [J]. THEORETICAL COMPUTER SCIENCE, 2022, 914 : 14 - 22
  • [24] 1,2-Dibromoethane on Cu(100): Bonding structure and transformation to C2H4
    Lin, Jong-Liang
    Lin, Yi-Shiue
    Shih, Jain-Jung
    Kuo, Kuan-Huang
    Lin, Shu-Kuan
    Wu, Tz-Shiuan
    Shiu, Ming-Yi
    [J]. JOURNAL OF CHEMICAL PHYSICS, 2011, 135 (06)
  • [25] Mitigation of Aging Product Generation in C4F7N-Based SF6 Alternatives: A Holistic Approach
    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
    [J]. ACS SUSTAINABLE CHEMISTRY & ENGINEERING, 2024, 12 (17) : 6467 - 6472
  • [26] Analysis of Decomposition Products of SF6 and C4F7N under Low Energy Corona Discharge
    Wei, Jia
    Park, Chanyeop
    Uzelac, Nenad
    Graber, Lukas
    [J]. 2020 IEEE ELECTRICAL INSULATION CONFERENCE (EIC), 2020, : 167 - 170
  • [27] 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
    Smirnov, Pavel
    Filatov, Evgeny
    Kuratieva, Natalia
    Plyusnin, Pavel
    Korenev, Sergey
    [J]. INTERNATIONAL JOURNAL OF MOLECULAR SCIENCES, 2023, 24 (15)
  • [28] 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
    Clauss, Corinna
    Schmidt, Horst
    Schwarzer, Anke
    Kroke, Edwin
    [J]. ZEITSCHRIFT FUR ANORGANISCHE UND ALLGEMEINE CHEMIE, 2011, 637 (14-15): : 2246 - 2251
  • [29] Enhancement of hydrocarbon recovery from CH4-C2H6-C3H8 mixed hydrates via gas sweep
    Zhang, Guobiao
    Sun, Youhong
    Li, Bing
    Shen, Yifeng
    Qi, Yun
    [J]. FUEL, 2022, 320
  • [30] Peculiarities of dehydroaromatization of CH4-C2H6 and CH4 over Mo/ZSM-5 catalysts
    Matus, Ekaterina V.
    Sukhova, Olga B.
    Ismagilov, Ilyas Z.
    Tsikoza, Lidiya T.
    Ismagilov, Zinfer R.
    [J]. REACTION KINETICS AND CATALYSIS LETTERS, 2009, 98 (01): : 59 - 67
12345