Recognition and isomorphism of tree-like \(P_4\)-connected graphs

DOI10.1016/S0166-218X(99)00140-7zbMath0935.05077MaRDI QIDQ1962050

Luitpold Babel

Publication date: 26 April 2000

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

zbMATH Keywords

recognitionisomorphism\(P_4\)-structure\(p\)-connected graphs\(p\)-trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

A time-based solution for the graph isomorphism problem, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weakly triangulated graphs
• Complement reducible graphs
• On a unique tree representation for \(P_ 4\)-extendible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• 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
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A Linear Recognition Algorithm for Cographs
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• P-Components and the Homogeneous Decomposition of Graphs