Recognizing the P₄-structure of block graphs

DOI10.1016/S0166-218X(99)00145-6MaRDI QIDQ1962056zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Van Bang Le

Publication date 16 July 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(99)00145-6

zbMATH Keywords

hypergraph

Mathematics Subject Classification ID

Perfect graphs (05C17) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

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.

Recommendations

• The P₄-structure of perfect graphs
• Recognizing the \(P_4\)-structure of bipartite graphs
• scientific article; zbMATH DE number 2119686
• Recognizing the \(P_ 4\)-structures of a tree
• On the structure of graphs with few P₄s

Cites work

• A semi-strong perfect graph theorem
• scientific article; zbMATH DE number 3887731 (Why is no real title available?)
• On the \(P_ 4\)-structure of perfect graphs. III: Partner decompositions
• Recognizing the \(P_ 4\)-structures of a tree

Cited in

(9)

• Recognizing the \(P_4\)-structure of bipartite graphs
• Recognizing the \(P_ 4\)-structures of a tree
• Perfect graphs with unique \(P_ 4\)-structure
• Bipartite-perfect graphs
• Recognizing well covered graphs of families with special \(P _{4}\)-components
• The P₄-structure of perfect graphs
• The A₄-structure of a graph
• scientific article; zbMATH DE number 1753165 (Why is no real title available?)
• scientific article; zbMATH DE number 2119686 (Why is no real title available?)

This page was built for publication: Recognizing the \(P_4\)-structure of block graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962056)