Recognizing the \(P_4\)-structure of block graphs (Q1962056): Difference between revisions

The \(P_4\)-structure of a graph \(G\) is the hypergraph on the same vertex set such that each hyperedge is a set of \(4\) vertices that induce a \(P_4\) in \(G\). It was conjectured by \textit{V. Chvátal} [Ann. Discrete Math. 21, 279-280 (1984; Zbl 0557.05043)] and proved by \textit{B. Reed} [J. Comb. Theory, Ser. B 43, 223-240 (1987; Zbl 0647.05052)] that a graph is perfect if it has the \(P_4\)-structure of a perfect graph. The authors give a polynomial time algorithm recognizing \(P_4\)-structures of block graphs, these are connected graphs in which all maximal \(2\)-connected subgraphs are complete.