Polynomial time recognition of P4-structure

ABSTRACT

A P4 is a set of four vertices of a graph that induces a chordless path; the P4-structure of a graph is the set of all P4's. Vašek Chvátal asked if there is a polynomial time algorithm to determine whether an arbitrary four-uniform hypergraph is the P4-structure of some graph. The answer is yes; we present such an algorithm.

REFERENCES

• 1: C. Berge, Färbung von Graphen deren sämtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe (1961), 114-115.
• 2: C. Berge and V. Chvátal (Eds.), "Topics on Perfect Graphs", Annals of Discrete Math.21, North-Holland, Amsterdam 1984.
• 3: A. Brandtstädt and V. B. Le, Split-perfect graphs: characterizations and algorithmic use, to appear in Disc. Appl. Math.
• 4: A. Brandtstädt, V. B. Le, S. Olariu, Recognizing the P4-structure of block-graphs. Technical Report Universität Rostock, 1996.
• 5: A. Brandtstädt, V. B. Le, S. Olariu, Linear-time recognition of the P4-structure of trees. Rutcors Research Report19-96 (1996).
• 6: V. Chvátal, Perfectly ordered graphs, in {2}.
• 7: V. Chvátal, C. T. Hoàng, On the P4-structure of perfect graphs I. Even decompositions, J. Combin. Theory Ser.B 39 (1985), 209-219.
• 8: V. Chvátal, On the P4-structure of perfect graphs. III. partner decompositions, Journal of Combinatorial Theory Series A, v.43 n.3, p.349-353, December 1, 1986
• 9: D. G. Corneil, Y. Perl, L. Stewart, Cographs: recognition, application and algorithms, Congr. Num. 43 (1984), 249-258.
• 10: Alain Cournier , Michel Habib, A New Linear Algorithm for Modular Decomposition, Proceedings of the 19th International Colloquium on Trees in Algebra and Programming, p.68-84, April 11-13, 1994
• 11: G. Ding, Recognizing the P4-structure of a tree, Graphs Combin.10 (1994), 323-328.
• 12: Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57), North-Holland, 2004
• 13: R. B. Hayward, On the P4-structure of perfect graphs. III. Weakly triangulated graphs, McGill University SOCS, Technical Report 83.20, Montreal, Canada, 1983.
• 14: Ryan B. Hayward, Recognizing P3-structure: a switching approach, Journal of Combinatorial Theory Series B, v.66 n.2, p.247-262, March 1996 [doi>10.1006/jctb.1996.0018]
• 15: R. B. Hayward , W. J. Lenhart, On the P4 structure of perfect graphs, Journal of Combinatorial Theory Series B, v.48 n.1, p.135-139, Feb. 1990 [doi>10.1016/0095-8956(90)90135-M]
• 16: R. B. Hayward, W. J. Lenhart, Bichromatic P4 Composition Schemes for Perfectly Orderable Graphs, manuscript.
• 17: C. T. Hoàng, On the P4-structure of perfect graphs II. Odd decompositions, J. Combin. Theory B 39 (1985), 220-232.
• 18: C. T. Hoàng, On the sibling-structure of perfect graphs, Journal of Combinatorial Theory Series B, v.49 n.2, p.282-286, Aug. 1990 [doi>10.1016/0095-8956(90)90031-T]
• 19: Chính T. Hoàng , Stefan Hougardy , Frédéric Maffray, On the P4-structure of perfect graphs: V. Overlap graphs, Journal of Combinatorial Theory Series B, v.67 n.2, p.212-237, July 1996 [doi>10.1006/jctb.1996.0042]
• 20: C. T. Hoàng & N. Khouzam, On brittle graphs, J. Graph Theory12 (1988) 391-404.
• 21: S. Hougardy, On the P4-Structure of Perfect Graphs, Shaker, Aachen, Germany 1996
• 22: L. Lovász, Normal hypergraphs and the Perfect Graph Conjecture, Discrete Math.2 (1972), 253-267.
• 23: Ross M. McConnell , Jeremy P. Spinrad, Linear-time modular decomposition and efficient transitive orientation of comparability graphs, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.536-545, January 23-25, 1994, Arlington, Virginia, United States
• 24: B. Reed, A semi-strong perfect graph theorem, Journal of Combinatorial Theory Series B, v.43 n.2, p.223-240, Oct. 1987 [doi>10.1016/0095-8956(87)90022-0]
• 25: D. Seinsche, On a property of the class of n-colorable graphs, J. Comb. Theory B 16 (1974), 191-193
• 26: Jeremy Spinrad, P4-trees and substitution decomposition, Discrete Applied Mathematics, v.39 n.3, p.263-291, Nov. 11, 1992 [doi>10.1016/0166-218X(92)90180-I]