Characterisation of $P_4$-free bipartite graphs (bipartite cographs)

An exercise in my lecture notes asks me to characterise all bipartite graphs that are $P_4$-free. I have attempted a solution which I will write up below, but the logic doesn't seem quite right to me, especially in the third paragraph.

If a graph $G$ is $P_4$-free, then it must be $(C_5,C_6,C_7,...)$-free, i.e. it does not contain a cycle of length larger than $4$ as an induced subgraph. This means that if $G$ has a cycle $C_n$ of odd length greater than $3$, it must contain $C_3$ as a subgraph. This is because $C_n$ cannot be chordless in $G$ (otherwise $C_n$ is an induced cycle of length larger than $4$), and as adding a chord to an odd cycle creates an odd cycle of shorter length, by induction we must have $C_3$ as a subgraph of $G$.

Therefore if a $P_4$-free graph is $C_3$-free, it will contain no cycle of odd length as a subgraph and will thus be bipartite (using the fact that a graph is bipartite if and only if it has no cycle of odd length as a subgraph). Conversely if a $P_4$-free graph contains $C_3$ it is clearly not bipartite by the above characterisation of bipartite graphs.

So the conclusion is that $P_4$-free bipartite graphs are precisely the $(C_3,P_4)$-free graphs.


You are right that they are indeed the $(C_3,P_4)$-free graphs, but I doubt that this is what was expected by the writer of these lecture notes. You should try to prove that a graph is a bipartite $P_4$-free graph if and only if each of its connected components is a complete bipartite graph. It can be proved as an application of the modular decomposition of $P_4$-free graphs, if this is explained in the lecture notes explain.

Regarding your proof, the direction $(P_4,C_3)$-free implies bipartite is correct. The reciprocal is immediate: A bipartite $P_4$-free graph is $C_3$-free, as you observed.