Recognizing the \(P_4\)-structure of block graphs
type: Item
instance of: scholarly article
title: Recognizing the \(P_4\)-structure of block graphs
zbMATH Open document ID: 0940.05033
DOI: 10.1016/S0166-218X(99)00145-6
author: Andreas Brandstädt
author: Van Bang Le
published in: Discrete Applied Mathematics
publication date: 2000-07-16T00:00:00Z
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.
Mathematics Subject Classification ID: 05C17
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1395023
zbMATH Keywords: hypergraph
MaRDI profile type: Publication
cites work: Q3222224
cites work: On the \(P_ 4\)-structure of perfect graphs. III: Partner decompositions
cites work: Recognizing the \(P_ 4\)-structures of a tree
cites work: A semi-strong perfect graph theorem
full work available at URL: s0166-218x(99)00145-6
OpenAlex ID: W2060080121
description: scientific article; zbMATH DE number 1395023