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 条
  • [1] Coloring graphs with forbidden induced subgraphs
    Chudnovsky, Maria
    PROCEEDINGS OF THE INTERNATIONAL CONGRESS OF MATHEMATICIANS (ICM 2014), VOL IV, 2014, : 291 - 302
  • [2] Star covers and star partitions of double-split graphs
    Mondal, Joyashree
    Vijayakumar, S.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2024, 47 (03)
  • [3] Star covers and star partitions of double-split graphs
    Joyashree Mondal
    S. Vijayakumar
    Journal of Combinatorial Optimization, 2024, 47
  • [4] Hitting forbidden induced subgraphs on bounded treewidth graphs
    Sau, Ignasi
    Souza, Ueverton dos Santos
    INFORMATION AND COMPUTATION, 2021, 281
  • [5] Forbidden subgraphs in generating graphs of finite groups
    Lucchini, Andrea
    Nemmi, Daniele
    ALGEBRAIC COMBINATORICS, 2022, 5 (05): : 925 - 946
  • [6] On forbidden induced subgraphs for K1,3-free perfect graphs
    Brause, Christoph
    Holub, Premysl
    Kabela, Adam
    Ryjacek, Zdenek
    Schiermeyer, Ingo
    Vrana, Petr
    DISCRETE MATHEMATICS, 2019, 342 (06) : 1602 - 1608
  • [7] The Game of Cops and Robbers on Directed Graphs with Forbidden Subgraphs
    Ming-rui Liu
    Mei Lu
    Acta Mathematicae Applicatae Sinica, English Series, 2022, 38 : 684 - 689
  • [8] The Game of Cops and Robbers on Directed Graphs with Forbidden Subgraphs
    Liu, Ming-rui
    Lu, Mei
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2022, 38 (03): : 684 - 689
  • [9] On coloring digraphs with forbidden induced subgraphs
    Steiner, Raphael
    JOURNAL OF GRAPH THEORY, 2023, 103 (02) : 323 - 339
  • [10] Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4
    Brause, Christoph
    Doanb, Trung Duy
    Holub, Premysl
    Kabela, Adam
    Ryjacek, Zdenek
    Schiermeyer, Ingo
    Vrana, Petr
    DISCRETE MATHEMATICS, 2022, 345 (06)
12345