Three-colourable perfect graphs without even pairs

Maria Chudnovsky; Paul Seymour

doi:10.1016/j.jctb.2011.11.005

Three-colourable perfect graphs without even pairs

Maria Chudnovsky, Paul Seymour

Mathematics

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

1 Scopus citations

Abstract

We still do not know how to construct the "most general" perfect graph, not even the most general three-colourable perfect graph. But constructing all perfect graphs with no even pairs seems easier, and here we make a start on it; we construct all three-connected three-colourable perfect graphs without even pairs and without clique cutsets. They are all either line graphs of bipartite graphs, or complements of such graphs.

Original language	English (US)
Pages (from-to)	363-394
Number of pages	32
Journal	Journal of Combinatorial Theory. Series B
Volume	102
Issue number	2
DOIs	https://doi.org/10.1016/j.jctb.2011.11.005
State	Published - Mar 2012

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

2-Join
Berge graphs
Perfect graphs

Access to Document

10.1016/j.jctb.2011.11.005

Cite this

@article{65bad8c4524b4524a4b8c32c98b0d0d1,

title = "Three-colourable perfect graphs without even pairs",

abstract = "We still do not know how to construct the {"}most general{"} perfect graph, not even the most general three-colourable perfect graph. But constructing all perfect graphs with no even pairs seems easier, and here we make a start on it; we construct all three-connected three-colourable perfect graphs without even pairs and without clique cutsets. They are all either line graphs of bipartite graphs, or complements of such graphs.",

keywords = "2-Join, Berge graphs, Perfect graphs",

author = "Maria Chudnovsky and Paul Seymour",

note = "Funding Information: E-mail address: [email protected] (P. Seymour). 1 This research was partially conducted while the author served as a Clay Mathematics Institute Research Fellow, and partially supported by NSF grant DMS-0758364. 2 Partially supported by ONR grant N00014-01-1-0608 and NSF grant DMS-0070912.",

year = "2012",

month = mar,

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

language = "English (US)",

volume = "102",

pages = "363--394",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Three-colourable perfect graphs without even pairs

AU - Chudnovsky, Maria

AU - Seymour, Paul

N1 - Funding Information: E-mail address: [email protected] (P. Seymour). 1 This research was partially conducted while the author served as a Clay Mathematics Institute Research Fellow, and partially supported by NSF grant DMS-0758364. 2 Partially supported by ONR grant N00014-01-1-0608 and NSF grant DMS-0070912.

PY - 2012/3

Y1 - 2012/3

N2 - We still do not know how to construct the "most general" perfect graph, not even the most general three-colourable perfect graph. But constructing all perfect graphs with no even pairs seems easier, and here we make a start on it; we construct all three-connected three-colourable perfect graphs without even pairs and without clique cutsets. They are all either line graphs of bipartite graphs, or complements of such graphs.

AB - We still do not know how to construct the "most general" perfect graph, not even the most general three-colourable perfect graph. But constructing all perfect graphs with no even pairs seems easier, and here we make a start on it; we construct all three-connected three-colourable perfect graphs without even pairs and without clique cutsets. They are all either line graphs of bipartite graphs, or complements of such graphs.

KW - 2-Join

KW - Berge graphs

KW - Perfect graphs

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

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

U2 - 10.1016/j.jctb.2011.11.005

DO - 10.1016/j.jctb.2011.11.005

M3 - Article

AN - SCOPUS:84856691101

SN - 0095-8956

VL - 102

SP - 363

EP - 394

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 2

ER -

Three-colourable perfect graphs without even pairs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this