Your query: an = (940.05033)
Answers 1-1 (of 1)
[New query form]
940.05033
Brandstaedt, Andreas; Le, Van Bang
Recognizing the $P_4$-structure of block graphs. (English)
[J] Discrete Appl. Math. 99, No.1-3, 349-366 (2000). [ISSN 0166-218X]
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 {\it V. Chv{a}tal} [Ann. Discrete Math. 21, 279-280 (1984; Zbl 557.05043)] and proved by {\it B. Reed} [J. Comb. Theory, Ser. B 43, 223-240 (1987; Zbl 647.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.
[ H.Mueller (Jena) ]
- MSC 1991:
-
*05C17 Perfect graphs
05C65 Hypergraphs
68R10 Graph theory in connection with computer science
05C85 Graphic algorithms
Keywords: hypergraph
Citations: Zbl 557.05043; Zbl 647.05052
Cited in Zbl. reviews...
[New query form]Answers 1-1 (of 1)
Zentralblatt MATH,
Copyright (c) 2000 European Mathematical Society, FIZ Karlsruhe & Springer-Verlag.