Even-hole-free graphs still have bisimplicial vertices

Maria Chudnovsky; Paul Seymour

doi:10.1016/j.jctb.2023.02.009

Even-hole-free graphs still have bisimplicial vertices

Maria Chudnovsky, Paul Seymour

Mathematics

Princeton University

Research output: Contribution to journal › Article › peer-review

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 language	American English
Pages (from-to)	331-381
Number of pages	51
Journal	Journal of Combinatorial Theory. Series B
Volume	161
DOIs	https://doi.org/10.1016/j.jctb.2023.02.009
State	Published - Jul 2023

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Bisimplicial vertex
Even-hole-free
Induced subgraph

Access to Document

10.1016/j.jctb.2023.02.009

Cite this

@article{fd3c30a4bfd840d2ab9198201587e3cb,

title = "Even-hole-free graphs still have bisimplicial vertices",

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.",

keywords = "Bisimplicial vertex, Even-hole-free, Induced subgraph",

author = "Maria Chudnovsky and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2023 Elsevier Inc.",

year = "2023",

month = jul,

doi = "10.1016/j.jctb.2023.02.009",

language = "American English",

volume = "161",

pages = "331--381",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Even-hole-free graphs still have bisimplicial vertices

AU - Chudnovsky, Maria

AU - Seymour, Paul

PY - 2023/7

Y1 - 2023/7

N2 - 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.

AB - 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.

KW - Bisimplicial vertex

KW - Even-hole-free

KW - Induced subgraph

UR - http://www.scopus.com/inward/record.url?scp=85150499640&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85150499640&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2023.02.009

DO - 10.1016/j.jctb.2023.02.009

M3 - Article

SN - 0095-8956

VL - 161

SP - 331

EP - 381

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Even-hole-free graphs still have bisimplicial vertices

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this