Bisimplicial vertices in even-hole-free graphs

Louigi Addario-Berry, Maria Chudnovsky, Frédéric Havet, Bruce Reed, Paul Seymour

Research output: Contribution to journalArticle

25 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1119-1164
Number of pages46
JournalJournal of Combinatorial Theory. Series B
Volume98
Issue number6
DOIs
StatePublished - Nov 2008

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Bisimplicial vertices
  • Colouring
  • Even holes
  • Induced subgraphs

Fingerprint Dive into the research topics of 'Bisimplicial vertices in even-hole-free graphs'. Together they form a unique fingerprint.

  • Cite this