Even pairs and prism corners in square-free Berge graphs

Maria Chudnovsky; Frédéric Maffray; Paul Seymour; Sophie Spirkl

doi:10.1016/j.jctb.2018.01.003

Even pairs and prism corners in square-free Berge graphs

Maria Chudnovsky
, Frédéric Maffray
, Paul Seymour
, Sophie Spirkl

Mathematics

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

2 Scopus citations

Abstract

Let G be a Berge graph such that no induced subgraph is a 4-cycle or a line-graph of a bipartite subdivision of K₄. We show that every such graph G either is a complete graph or has an even pair.

Original language	English (US)
Pages (from-to)	12-39
Number of pages	28
Journal	Journal of Combinatorial Theory. Series B
Volume	131
DOIs	https://doi.org/10.1016/j.jctb.2018.01.003
State	Published - Jul 2018

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Berge graphs
Even pairs
Perfect graphs
Prisms
Square-free

Access to Document

10.1016/j.jctb.2018.01.003

Cite this

@article{b63d31220e6f412ea329a087781c1633,

title = "Even pairs and prism corners in square-free Berge graphs",

abstract = "Let G be a Berge graph such that no induced subgraph is a 4-cycle or a line-graph of a bipartite subdivision of K4. We show that every such graph G either is a complete graph or has an even pair.",

keywords = "Berge graphs, Even pairs, Perfect graphs, Prisms, Square-free",

author = "Maria Chudnovsky and Fr{\'e}d{\'e}ric Maffray and Paul Seymour and Sophie Spirkl",

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

year = "2018",

month = jul,

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

language = "English (US)",

volume = "131",

pages = "12--39",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Even pairs and prism corners in square-free Berge graphs

AU - Chudnovsky, Maria

AU - Maffray, Frédéric

AU - Seymour, Paul

AU - Spirkl, Sophie

PY - 2018/7

Y1 - 2018/7

N2 - Let G be a Berge graph such that no induced subgraph is a 4-cycle or a line-graph of a bipartite subdivision of K4. We show that every such graph G either is a complete graph or has an even pair.

AB - Let G be a Berge graph such that no induced subgraph is a 4-cycle or a line-graph of a bipartite subdivision of K4. We show that every such graph G either is a complete graph or has an even pair.

KW - Berge graphs

KW - Even pairs

KW - Perfect graphs

KW - Prisms

KW - Square-free

UR - https://www.scopus.com/pages/publications/85040571182

UR - https://www.scopus.com/pages/publications/85040571182#tab=citedBy

U2 - 10.1016/j.jctb.2018.01.003

DO - 10.1016/j.jctb.2018.01.003

M3 - Article

AN - SCOPUS:85040571182

SN - 0095-8956

VL - 131

SP - 12

EP - 39

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Even pairs and prism corners in square-free Berge graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this