What are prime $ P_4 $-free graphs?

192 Views Asked by At

Well, I know what prime graphs are and what $ P_4 $ is (and that $ P_4 $-free graphs are precisely the cographs; i.e. all their induced subgraphs on two or more vertices are either disconnected or have disconnected complement). But I'm stumped by an exercise in my notes which simply says "describe prime $ P_4 $-free graphs". I don't really know where to begin with this one. Only thought is that primeness is a property closed under taking complements, since a module in a graph will also be a module in its complement. So suppose that a $ P_4 $-free graph $ G $ is prime. Wlog we can assume $ G $ to be disconnected. Then we'll need all of its connected components to be prime (obviously any non-trivial modules will have to be contained within a single component). But each of these components has disconnected complement, and we'll need all the components of those to be prime. And so on. This gives us some restrictions, but I'm not sure how to use them.