On a unique tree representation for \(P_ 4\)-extendible graphs

DOI10.1016/0166-218X(91)90085-BzbMath0754.05051MaRDI QIDQ1182318

S. Singh

Publication date: 28 June 1992

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

zbMATH Keywords

polynomial algorithm; cographs; tree representation; \(P_ 4\)-extendible graphs

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

05C75: Structural characterization of families of graphs

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

Triangulating graphs with few \(P_4\)'s, On the structure of graphs with few \(P_4\)s, Tree-like \(P_4\)-connected graphs, Hamiltonicity in graphs with few \(P_ 4\)'s, \(N\)-extendible posets, and how to minimize total weighted completion time, Recognition and isomorphism of tree-like \(P_4\)-connected graphs, On the \(P_4\)-components of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A tree representation for \(P_ 4\)-sparse graphs
• On a property of the class of n-colorable graphs
• Linear Algorithms for Isomorphism of Maximal Outerplanar Graphs
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A Linear Recognition Algorithm for Cographs
• On the tree representation of chordal graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism