Take the 2-minute tour ×

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.

share|improve this question
See the ISGCI for questions of this kind. wwwteo.informatik.uni-rostock.de/isgci –  András Salamon Jul 28 '10 at 15:22
Wow. That is an impressive database. –  Stefan Geschke Jul 29 '10 at 13:04

2 Answers 2

up vote 11 down vote accepted

These P4-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.)

share|improve this answer
Wikipedia page is not bad: en.wikipedia.org/wiki/Cograph –  Emil Jul 28 '10 at 19:05
Thanks Emil! $\mbox{}$ –  François G. Dorais Jul 28 '10 at 20:13

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/

share|improve this answer
Yes, I was looking for a proof without observing Berge-ness. –  Stefan Geschke Jul 24 '10 at 21:33

Your Answer


