Skip to main content

Three-colourable perfect graphs without even pairs

Author(s): Chudnovsky, Maria; Seymour, Paul D.

To refer to this page use:
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. (C) 2012 Elsevier Inc. All rights reserved.
Publication Date: Mar-2012
Electronic Publication Date: 10-Jan-2012
Citation: Chudnovsky, Maria, Seymour, Paul. (2012). Three-colourable perfect graphs without even pairs. JOURNAL OF COMBINATORIAL THEORY SERIES B, 102 (363 - 394. doi:10.1016/j.jctb.2011.11.005
DOI: doi:10.1016/j.jctb.2011.11.005
ISSN: 0095-8956
Pages: 363 - 394
Type of Material: Journal Article
Version: Final published version. Article is made available in OAR by the publisher's permission or policy.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.