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 条
  • [41] Sparse induced subgraphs of large treewidth
    Bonnet, Edouard
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2025, 173 : 184 - 203
  • [42] Counting Small Induced Subgraphs with Hereditary Properties
    Focke, Jacob
    Roth, Marc
    PROCEEDINGS OF THE 54TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '22), 2022, : 1543 - 1551
  • [43] COUNTING SMALL INDUCED SUBGRAPHS WITH HEREDITARY PROPERTIES
    Focke, Jacob
    Roth, Marc
    SIAM JOURNAL ON COMPUTING, 2024, 53 (02) : 189 - 220
  • [44] On the forbidden induced subgraph sandwich problem
    Dantas, Simone
    de Figueiredo, Celina M. H.
    da Silva, Murilo V. G.
    Teixeira, Rafael B.
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (16) : 1717 - 1725
  • [45] Split-perfect graphs:: Characterizations and algorithmic use
    Brandstädt, A
    Le, VB
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2004, 17 (03) : 341 - 360
  • [46] CONSTANT-TIME PARALLEL RECOGNITION OF SPLIT GRAPHS
    NIKOLOPOULOS, SD
    INFORMATION PROCESSING LETTERS, 1995, 54 (01) : 1 - 8
  • [47] Counting Small Induced Subgraphs Satisfying Monotone Properties
    Roth, Marc
    Schmitt, Johannes
    Wellnitz, Philip
    2020 IEEE 61ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2020), 2020, : 1356 - 1367
  • [48] Forbidden induced subgraph characterization of cograph contractions
    Zverovich, IE
    Zverovich, II
    JOURNAL OF GRAPH THEORY, 2004, 46 (03) : 217 - 226
  • [49] Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs
    Ning, Bo
    Zhang, Shenggui
    DISCRETE MATHEMATICS, 2013, 313 (17) : 1715 - 1725
  • [50] Maximum-size subgraphs of P4-sparse graphs admitting a perfect matching
    Nikolopoulos, SD
    Palios, L
    ADVANCES IN INFORMATICS, PROCEEDINGS, 2005, 3746 : 68 - 79
12345