Simple proof that these graphs are perfect

Question

I recently came across a family of infinite graphs (in the context of two-dimensional convexity) that don't have induced 4-paths (paths with 4 vertices). Note that the complement of a 4-path is again a 4-path.
Clearly, every induced $n+1$-cycle contains an induced $n$-path.
Hence, by the Strong Perfect Graph Theorem of Chudnowski, Robertson, Seymour, and Thomas, graphs without induced 4-paths are perfect.

Can anyone provide a simple proof of that fact?
Having no induced 4-paths seems like a very strong condition.

Answer 1

These P₄-free graphs are also known as cographs. A simple proof of the perfectness of such graphs was given by Seinsche, On a property of the class of n-colorable graphs, J. Comb. Th. Ser. B 16 (1974), 191–193. MR0337679 The key to the proof is the fact that these graphs are also characterized by the property that every subset of $V(G)$ with more than one element is either not $G$-connected or not $\overline{G}$-connected. It follows that every such graph can be obtained from a single vertex by repeatedly duplicating vertices with or without an edge between the two duplicates. Since these two duplication operations preserve perfectness, all such graphs are perfect. (This quick argument is due to Lovász.)

Answer 2

It might be possible to prove that such graphs are perfect without first observing that they are Berge and applying the SPG Theorem, but I suspect this would be hard. It has been noted that the property of being Berge can be completely encoded in the "$P_4$-structure" (the $4$-uniform hypergraph of all induced paths of length $4$).

You can find necessary and sufficient conditions for a graph to be Berge, in terms of its $P_4$-structure here: http://www.aimath.org/WWN/perfectgraph/articles/html/52a/

This is part of a larger collection of open problems on perfect graphs: http://www.aimath.org/WWN/perfectgraph/