Even-hole-free graphs still have bisimplicial vertices

Research output: Contribution to journalArticlepeer-review

4 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 an earlier paper [1], Addario-Berry, Havet and Reed, with the authors, claimed to prove a conjecture of Reed, that every even-hole-free graph has a bisimplicial vertex, but we have recently been shown that the “proof” has a serious error. Here we give a proof using a different approach.

Original languageEnglish (US)
Pages (from-to)331-381
Number of pages51
JournalJournal of Combinatorial Theory. Series B
Volume161
DOIs
StatePublished - Jul 2023

All Science Journal Classification (ASJC) codes

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

Keywords

  • Bisimplicial vertex
  • Even-hole-free
  • Induced subgraph

Fingerprint

Dive into the research topics of 'Even-hole-free graphs still have bisimplicial vertices'. Together they form a unique fingerprint.

Cite this