The \(P_4\)-structure of perfect graphs (Q2758334)

This papers surveys earlier results on perfect graphs that are based on the \(P_4\)-structure. The \(P_4\)-structure of graph \(G\) is a \(4\)-uniform hypergraph on \(V(G)\), one hyperedge for each spanned path on \(4\) vertices. The semi-strong perfect graph theorem of Reed states that a graph is perfect if and only if it has the \(P_4\)-structure of a perfect graph. This explains the importance of the notion. It is mentioned that the \(P_4\)-isomorphism problem is polynomially equivalent with the graph-isomorphism problem, hence NP-complete. The problem of perfect graph recognition is related to perfect \(P_4\)-structure recognition, but the complexity of this latter problem is not know. However, \(P_4\)-structure recognition (i.e. whether a \(4\)-uniform graph is the \(P_4\)-structure of a graph) can be solved in polynomial time. The paper ends with some properties of the \(P_3\)-structure of graphs.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00015].