• Title of article

    Bisimplicial vertices in even-hole-free graphs

  • Author/Authors

    Addario-Berry، نويسنده , , Louigi and Chudnovsky، نويسنده , , Maria and Havet، نويسنده , , Frédéric and Reed، نويسنده , , Bruce and Seymour، نويسنده , , Paul، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2008
  • Pages
    46
  • From page
    1119
  • To page
    1164
  • Abstract
    A hole in a graph is an induced subgraph which is a cycle of length at least four. A hole is called even if it has an even number of vertices. An even-hole-free graph is a graph with no even holes. A vertex of a graph is bisimplicial if the set of its neighbours is the union of two cliques. In this paper we prove that every even-hole-free graph has a bisimplicial vertex, which was originally conjectured by Reed.
  • Keywords
    induced subgraphs , Bisimplicial vertices , Even holes , Colouring
  • Journal title
    Journal of Combinatorial Theory Series B
  • Serial Year
    2008
  • Journal title
    Journal of Combinatorial Theory Series B
  • Record number

    1528754