FORBIDDEN INDUCED SUBGRAPHS OF DOUBLE-SPLIT GRAPHS

被引：3
|
作者：
Alexeev, Boris [1 ]
Fradkin, Alexandra [1 ]
Kim, Ilhee [1 ]
机构：
[1] Princeton Univ, Dept Math, Princeton, NJ 08540 USA
来源：
SIAM JOURNAL ON DISCRETE MATHEMATICS | 2012年 / 26卷 / 01期
关键词：
induced subgraphs; perfect graphs; graph families; double-split graphs;
D O I：
10.1137/100818121
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In the course of proving the strong perfect graph theorem, Chudnovsky, Robertson, Seymour, and Thomas showed that every perfect graph either belongs to one of five basic classes or admits one of several decompositions. Four of the basic classes are closed under the operation of taking induced subgraphs (and have known forbidden subgraph characterizations), while the fifth one, consisting of double-split graphs, is not. A graph is doubled if it is an induced subgraph of a double-split graph. We find the forbidden induced subgraph characterization of doubled graphs; it contains 44 graphs.
引用
收藏
页码：1 / 14
页数：14
相关论文
共 50 条
  • [31] On minimal forbidden subgraph characterizations of balanced graphs
    Bonomo, Flavia
    Duran, Guillermo
    Safe, Martin D.
    Wagler, Annegret K.
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (13-14) : 1925 - 1942
  • [32] Induced Subgraphs With Distinct Sizes
    Alon, Noga
    Kostochka, A. V.
    RANDOM STRUCTURES & ALGORITHMS, 2009, 34 (01) : 45 - 53
  • [33] Induced subgraphs of prescribed size
    Alon, N
    Krivelevich, M
    Sudakov, B
    JOURNAL OF GRAPH THEORY, 2003, 43 (04) : 239 - 251
  • [34] On induced subgraphs of the Hamming graph
    Dong, Dingding
    JOURNAL OF GRAPH THEORY, 2021, 96 (01) : 160 - 166
  • [35] DISTINCT DEGREES IN INDUCED SUBGRAPHS
    Jenssen, Matthew
    Keevash, Peter
    Long, Eoin
    Yepremyan, Liana
    PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2020, 148 (09) : 3835 - 3846
  • [36] Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs
    Chaniotis, Aristotelis
    Qu, Zishen
    Spirkl, Sophie
    DISCRETE MATHEMATICS, 2023, 346 (03)
  • [37] Recognition of Unipolar and Generalised Split Graphs
    McDiarmid, Colin
    Yolov, Nikola
    ALGORITHMS, 2015, 8 (01) : 46 - 59
  • [38] Improvements on Induced Subgraphs of Given Sizes
    He, Jialin
    Ma, Jie
    Zhao, Lilu
    COMMUNICATIONS IN MATHEMATICS AND STATISTICS, 2023,
  • [39] Induced subgraphs of a tree with constraint degree
    Wang, Tao
    Wu, Baoyindureng
    APPLIED MATHEMATICS AND COMPUTATION, 2023, 440
  • [40] LARGE NEARLY REGULAR INDUCED SUBGRAPHS
    Alon, Noga
    Krivelevich, Michael
    Sudakov, Benny
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 22 (04) : 1325 - 1337
12345