On the \(P_ 4\)-structure of perfect graphs. V: Overlap graphs (Q1924145)

An odd hole in a graph is an induced cycle with length odd and at least 5. A Berge graph is a graph with no odd hole or its complement. The \(k\)-overlap graph of a graph \(G\) has a vertex for each induced \(P_4\) in \(G\), and two vertices are adjacent if the corresponding \(P_4\)'s have exactly \(k\) vertices of \(G\) in common. Here \(P_4\) denotes the path with 4 vertices. It is shown that for \(k=2,3\), if the \(k\)-overlap graph of a Berge graph is triangle-free then \(G\) is perfect. This yields that if the 3-overlap graph of \(G\) is bipartite then \(G\) is perfect, and if \(G\) is \(C_5\)-free and the 2-overlap graph of \(G\) is bipartite then \(G\) is perfect. Similarly, if \(G\) is \(C_5\)-free and the 1-overlap graph is bipartite then \(G\) is perfect. The result for \(k=3\) extends some recent work on `partner graphs'.