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 条
  • [21] Graphs having small number of sizes on induced k-subgraphs
    Axenovich, Maria
    Balogh, Jozsef
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2007, 21 (01) : 264 - 272
  • [22] Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
    Barnaby Martin
    Daniël Paulusma
    Siani Smith
    Erik Jan van Leeuwen
    Algorithmica, 2023, 85 : 2580 - 2604
  • [23] NORDHAUS-GADDUM INEQUALITIES FOR THE NUMBER OF CONNECTED INDUCED SUBGRAPHS IN GRAPHS
    Andriantiana, Eric O. D.
    Dossou-Olory, Audace A. V.
    QUAESTIONES MATHEMATICAE, 2022, 45 (08) : 1191 - 1213
  • [24] Induced subgraphs and tree decompositions VI. Graphs with 2-cutsets
    Abrishami, Tara
    Chudnovsky, Maria
    Hajebi, Sepehr
    Spirkl, Sophie
    DISCRETE MATHEMATICS, 2025, 348 (01)
  • [25] Induced Subgraphs of Induced Subgraphs of Large Chromatic Number
    Girao, Antonio
    Illingworth, Freddie
    Powierski, Emil
    Savery, Michael
    Scott, Alex
    Tamitegama, Youri
    Tan, Jane
    COMBINATORICA, 2024, 44 (01) : 37 - 62
  • [26] Induced Subgraphs of Induced Subgraphs of Large Chromatic Number
    António Girão
    Freddie Illingworth
    Emil Powierski
    Michael Savery
    Alex Scott
    Youri Tamitegama
    Jane Tan
    Combinatorica, 2024, 44 : 37 - 62
  • [27] Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes
    Scott, Alex
    Seymour, Paul
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2018, 132 : 180 - 235
  • [28] Induced subgraphs of graphs with large chromatic number. I. Odd holes
    Scott, Alex
    Seymour, Paul
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2016, 121 : 68 - 84
  • [29] Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs
    Cheriyan, Joseph
    Hajebi, Sepehr
    Qu, Zishen
    Spirkl, Sophie
    DISCRETE MATHEMATICS, 2022, 345 (07)
  • [30] Induced subgraphs of graphs with large chromatic number. VII. Gyarfas' complementation conjecture
    Scott, Alex
    Seymour, Paul
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 142 : 43 - 55
12345