Three-colourable perfect graphs without even pairs

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

Download

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1m673

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
Journal/Proceeding Title:	JOURNAL OF COMBINATORIAL THEORY SERIES B
Version:	Final published version. Article is made available in OAR by the publisher's permission or policy.