Corrigendum to “Bisimplicial vertices in even-hole-free graphs” (Bisimplicial vertices in even-hole-free graphs (2008) 98(6) (1119–1164), (S0095895608000087), (10.1016/j.jctb.2007.12.006))

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

doi:10.1016/j.jctb.2020.02.001

Corrigendum to “Bisimplicial vertices in even-hole-free graphs” (Bisimplicial vertices in even-hole-free graphs (2008) 98(6) (1119–1164), (S0095895608000087), (10.1016/j.jctb.2007.12.006))

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

Mathematics

Princeton University

Research output: Contribution to journal › Comment/debate › peer-review

1 Scopus citations

Abstract

An even-hole-free graph is a graph with no induced cycle of even length. A vertex of a graph is bisimplicial if the set of its neighbours is the union of two cliques. Reed conjectured in [3] that every nonnull even-hole-free graph has a bisimplicial vertex. The authors published a paper [1] in which they claimed a proof, but there is a serious mistake in that paper, recently brought to our attention by Rong Wu. The error in [1] is in the last line of the proof of theorem 3.1 of that paper: we say “it follows that [Formula presented], and so v is bisimplicial in G”; and this is not correct, since cliques of [Formula presented] may not be cliques of G. Unfortunately, the flawed theorem 3.1 is fundamental to much of the remainder of the paper, and we have not been able to fix the error (although we still believe 3.1 to be true). Thus, this paper does not prove Reed's conjecture after all. Two of us (Chudnovsky and Seymour) claim to have a proof of Reed's conjecture using a different method [2].

Original language	American English
Pages (from-to)	374-375
Number of pages	2
Journal	Journal of Combinatorial Theory. Series B
Volume	142
DOIs	https://doi.org/10.1016/j.jctb.2020.02.001
State	Published - May 2020

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jctb.2020.02.001

Cite this

Addario-Berry, L., Chudnovsky, M., Havet, F., Reed, B., & Seymour, P. (2020). Corrigendum to “Bisimplicial vertices in even-hole-free graphs” (Bisimplicial vertices in even-hole-free graphs (2008) 98(6) (1119–1164), (S0095895608000087), (10.1016/j.jctb.2007.12.006)). Journal of Combinatorial Theory. Series B, 142, 374-375. https://doi.org/10.1016/j.jctb.2020.02.001

@article{e9b7b1f25140441892d6dbd18c2a066a,

title = "Corrigendum to “Bisimplicial vertices in even-hole-free graphs” (Bisimplicial vertices in even-hole-free graphs (2008) 98(6) (1119–1164), (S0095895608000087), (10.1016/j.jctb.2007.12.006))",

abstract = "An even-hole-free graph is a graph with no induced cycle of even length. A vertex of a graph is bisimplicial if the set of its neighbours is the union of two cliques. Reed conjectured in [3] that every nonnull even-hole-free graph has a bisimplicial vertex. The authors published a paper [1] in which they claimed a proof, but there is a serious mistake in that paper, recently brought to our attention by Rong Wu. The error in [1] is in the last line of the proof of theorem 3.1 of that paper: we say “it follows that [Formula presented], and so v is bisimplicial in G”; and this is not correct, since cliques of [Formula presented] may not be cliques of G. Unfortunately, the flawed theorem 3.1 is fundamental to much of the remainder of the paper, and we have not been able to fix the error (although we still believe 3.1 to be true). Thus, this paper does not prove Reed's conjecture after all. Two of us (Chudnovsky and Seymour) claim to have a proof of Reed's conjecture using a different method [2].",

author = "Louigi Addario-Berry and Maria Chudnovsky and Fr{\'e}d{\'e}ric Havet and Bruce Reed and Paul Seymour",

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

year = "2020",

month = may,

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

language = "American English",

volume = "142",

pages = "374--375",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

Addario-Berry, L, Chudnovsky, M, Havet, F, Reed, B & Seymour, P 2020, 'Corrigendum to “Bisimplicial vertices in even-hole-free graphs” (Bisimplicial vertices in even-hole-free graphs (2008) 98(6) (1119–1164), (S0095895608000087), (10.1016/j.jctb.2007.12.006))', Journal of Combinatorial Theory. Series B, vol. 142, pp. 374-375. https://doi.org/10.1016/j.jctb.2020.02.001

Corrigendum to “Bisimplicial vertices in even-hole-free graphs” (Bisimplicial vertices in even-hole-free graphs (2008) 98(6) (1119–1164), (S0095895608000087), (10.1016/j.jctb.2007.12.006)). / Addario-Berry, Louigi; Chudnovsky, Maria; Havet, Frédéric et al.
In: Journal of Combinatorial Theory. Series B, Vol. 142, 05.2020, p. 374-375.

Research output: Contribution to journal › Comment/debate › peer-review

TY - JOUR

T1 - Corrigendum to “Bisimplicial vertices in even-hole-free graphs” (Bisimplicial vertices in even-hole-free graphs (2008) 98(6) (1119–1164), (S0095895608000087), (10.1016/j.jctb.2007.12.006))

AU - Addario-Berry, Louigi

AU - Chudnovsky, Maria

AU - Havet, Frédéric

AU - Reed, Bruce

AU - Seymour, Paul

PY - 2020/5

Y1 - 2020/5

N2 - An even-hole-free graph is a graph with no induced cycle of even length. A vertex of a graph is bisimplicial if the set of its neighbours is the union of two cliques. Reed conjectured in [3] that every nonnull even-hole-free graph has a bisimplicial vertex. The authors published a paper [1] in which they claimed a proof, but there is a serious mistake in that paper, recently brought to our attention by Rong Wu. The error in [1] is in the last line of the proof of theorem 3.1 of that paper: we say “it follows that [Formula presented], and so v is bisimplicial in G”; and this is not correct, since cliques of [Formula presented] may not be cliques of G. Unfortunately, the flawed theorem 3.1 is fundamental to much of the remainder of the paper, and we have not been able to fix the error (although we still believe 3.1 to be true). Thus, this paper does not prove Reed's conjecture after all. Two of us (Chudnovsky and Seymour) claim to have a proof of Reed's conjecture using a different method [2].

AB - An even-hole-free graph is a graph with no induced cycle of even length. A vertex of a graph is bisimplicial if the set of its neighbours is the union of two cliques. Reed conjectured in [3] that every nonnull even-hole-free graph has a bisimplicial vertex. The authors published a paper [1] in which they claimed a proof, but there is a serious mistake in that paper, recently brought to our attention by Rong Wu. The error in [1] is in the last line of the proof of theorem 3.1 of that paper: we say “it follows that [Formula presented], and so v is bisimplicial in G”; and this is not correct, since cliques of [Formula presented] may not be cliques of G. Unfortunately, the flawed theorem 3.1 is fundamental to much of the remainder of the paper, and we have not been able to fix the error (although we still believe 3.1 to be true). Thus, this paper does not prove Reed's conjecture after all. Two of us (Chudnovsky and Seymour) claim to have a proof of Reed's conjecture using a different method [2].

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

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

U2 - 10.1016/j.jctb.2020.02.001

DO - 10.1016/j.jctb.2020.02.001

M3 - Comment/debate

SN - 0095-8956

VL - 142

SP - 374

EP - 375

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Corrigendum to “Bisimplicial vertices in even-hole-free graphs” (Bisimplicial vertices in even-hole-free graphs (2008) 98(6) (1119–1164), (S0095895608000087), (10.1016/j.jctb.2007.12.006))

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this