Topics on Perfect Graphs

C. Berge and V. Chvátal (Eds.)044486587X, 9780444865878, 9780080871998

Table of contents :
Content:
Advisory Editors
Page ii

Edited by
Page iii

Copyright page
Page iv

Introduction
Pages vii-xiv

Minimax Theorems for Normal Hypergraphs and Balanced Hypergraphs — A Survey Original Research Article
Pages 3-19
C. Berge

A Class of Bichromatic Hypergraphs Original Research Article
Pages 21-27
Jean-Claude Fournier, Michel Las Vergnas

Normal Hypergraphs and the Weak Perfect Graph Conjecture Original Research Article
Pages 29-42
L. Lovász

Diperfect Graphs Original Research Article
Pages 45-56
Claude Berge

Strongly Perfect Graphs Original Research Article
Pages 57-61
C. Berge, P. Duchet

Perfectly Ordered Graphs Original Research Article
Pages 63-65
V. Chvátal

Classical Perfect Graphs: An introduction with emphasis on triangulated and interval graphs Original Research Article
Pages 67-96
Pierre Duchet

The Perfect Graph Conjecture for Toroidal Graphs Original Research Article
Pages 97-101
Charles Grinstead

The Perfect Graph Conjecture on Special Graphs — A Survey Original Research Article
Pages 103-113
Wen-Lian Hsu

The Graphs Whose Odd Cycles have at Least two Chords Original Research Article
Pages 115-119
H. Meyniel

Contributions to a Characterization of the Structure of Perfect Graphs Original Research Article
Pages 121-144
Elefterie Olaru, Horst Sachs

Meyniel’s Graphs are Strongly Perfect Original Research Article
Pages 145-148
G. Ravindra

The Validity of the Perfect Graph Conjecture for K4-Free Graphs Original Research Article
Pages 149-157
Alan Tucker

The Strong Perfect Graph Theorem for a Class of Partitionable Graphs Original Research Article
Pages 161-167
Rick Giles, L.E. Trotter Jr., Alan Tucker

A Characterization of Perfect Matrices Original Research Article
Pages 169-178
Manfred W. Padberg

Graphical Properties Related to Minimal Imperfection Original Research Article
Pages 181-192
R.G. Bland, H.-C. Huang, L.E. Trotter Jr.

An Equivalent Version of the Strong Perfect Graph Conjecture Original Research Article
Pages 193-195
V. Chvátal

Combinatorial Designs Related to the Perfect Graph Conjecture Original Research Article
Pages 197-206
V. Chvátal, R.L. Graham, A.F. Perold, S.H. Whitesides

A Classification of Certain Graphs with Minimal Imperfection Properties Original Research Article
Pages 207-218
S.H. Whitesides

A Composition for Perfect Graphs Original Research Article
Pages 221-224
Robert E. Bixby

Polynomial Algorithm to Recognize a Meyniel Graph Original Research Article
Pages 225-252
M. Burlet, J. Fonlupt

Parity Graphs Original Research Article
Pages 253-277
M. Burlet, J.P. Uhry

A Semi-Strong Perfect Graph Conjecture Original Research Article
Pages 279-280
V. Chvátal

A Method for Solving Certain Graph Recognition and Optimization Problems, with Applications to Perfect Graphs Original Research Article
Pages 281-297
Sue H. Whitesides

Algorithmic Aspects of Perfect Graphs Original Research Article
Pages 301-323
Martin Charles Golumbic

Polynomial Algorithms for Perfect Graphs Original Research Article
Pages 325-356
M. Grötschel, L. Lovász, A. Schrijver

Algorithms for Maximum Weight Cliques, Minimum Weighted Clique Covers and Minimum Colorings of Claw-Free Perfect Graphs Original Research Article
Pages 357-369
Wen-Lian Hsu, George L. Nemhauser