Bisimplicial vertices in even-hole-free graphs

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

doi:10.1016/j.jctb.2007.12.006

Bisimplicial vertices in even-hole-free graphs

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

Mathematics

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

37 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 language	English (US)
Pages (from-to)	1119-1164
Number of pages	46
Journal	Journal of Combinatorial Theory. Series B
Volume	98
Issue number	6
DOIs	https://doi.org/10.1016/j.jctb.2007.12.006
State	Published - 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

Access to Document

10.1016/j.jctb.2007.12.006

Cite this

@article{5179f34a1ded455e99f3257d8ec13346,

title = "Bisimplicial vertices in even-hole-free graphs",

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 = "Bisimplicial vertices, Colouring, Even holes, Induced subgraphs",

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

year = "2008",

month = nov,

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

language = "English (US)",

volume = "98",

pages = "1119--1164",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "6",

}

TY - JOUR

T1 - Bisimplicial vertices in even-hole-free graphs

AU - Addario-Berry, Louigi

AU - Chudnovsky, Maria

AU - Havet, Frédéric

AU - Reed, Bruce

AU - Seymour, Paul

PY - 2008/11

Y1 - 2008/11

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 this paper we prove that every even-hole-free graph has a bisimplicial vertex, which was originally conjectured by Reed.

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 this paper we prove that every even-hole-free graph has a bisimplicial vertex, which was originally conjectured by Reed.

KW - Bisimplicial vertices

KW - Colouring

KW - Even holes

KW - Induced subgraphs

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

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

U2 - 10.1016/j.jctb.2007.12.006

DO - 10.1016/j.jctb.2007.12.006

M3 - Article

SN - 0095-8956

VL - 98

SP - 1119

EP - 1164

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 6

ER -

Bisimplicial vertices in even-hole-free graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this