Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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
add comment

2 Answers

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
add comment

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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.