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

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:

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.

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.