Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs
type: Item
instance of: scholarly article
title: Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs
zbMATH Open document ID: 1030.05049
DOI: 10.1016/S0095-8956(02)00021-7
author: Michele Conforti
author: Gérard Cornuéjols
published in: Journal of Combinatorial Theory. Series B
publication date: 2003-08-25T00:00:00Z
review text: A hole is a cordless cycle of length at least four. A hole is odd if it has an odd number of vertices. The strong perfect graph conjecture states that a graph \(G\) is perfect if neither \(G\) nor \(\overline G\) has an odd hole. The authors prove the conjecture for graphs that do not contain parachutes and proper wheels. Recently, \textit{M. Chudnovsky}, \textit{N. Robertson}, \textit{P. D. Seymoud} and \textit{R. Thomas} [Math. Program. 97B, 405-422 (2002; Zbl 1028.05035)] proved the conjecture for all graphs.
Mathematics Subject Classification ID: 05C17
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1970694
zbMATH Keywords: Perfect graph
zbMATH Keywords: Odd hole
zbMATH Keywords: Strong perfect graph conjecture
zbMATH Keywords: Decomposition
zbMATH Keywords: Star cutset
zbMATH Keywords: 2-join
zbMATH Keywords: Meyniel graph
zbMATH Keywords: Line graph of bipartite graph
reviewed by: G. Gutin
MaRDI profile type: Publication
cites work: Q3222886
cites work: The strong perfect graph theorem
cites work: Star-cutsets and perfect graphs
cites work: Perfect graphs, partitionable graphs and cutsets
cites work: A mickey-mouse decomposition theorem
cites work: Even and odd holes in cap-free graphs
cites work: A theorem of Truemper
cites work: Compositions for perfect graphs
cites work: A Combinatorial Decomposition Theory
cites work: A description of claw-free perfect graphs
cites work: On the perfect graph conjecture
cites work: Alpha-balanced graphs and matrices and GF(3)-representability of matroids
description: scientific article; zbMATH DE number 1970694