Graphs without Odd Holes, Parachutes or Proper Wheels: a Generalization of Meyniel Graphs and of Line Graphs of Bipartite Graphs

<p>We prove that the strong perfect graph conjecture holds for graphs that do not contain parachutes or proper wheels. This is done by showing the following theorem:</p> <p><em>If a graph G contains no odd hole, no parachute and no proper wheel, then G is bipartite or the line graph of a bipartite graph or G contains a star cutset or an extended strong 2-join or Ḡ is disconnected.</em></p> <p>To prove this theorem, we prove two decomposition theorems which are interesting in their own rights. The first is a generalization of the Burlet–Fonlupt decomposition of Meyniel graphs by clique cutsets and amalgams. The second is a precursor of the recent decomposition theorem of Chudnovsky, Robertson, Seymour and Thomas for Berge graphs that contain a line graph of a bipartite subdivision of a 3-connected graph.</p>