Recognition and isomorphism of tree-like \(P_4\)-connected graphs
type: Item
instance of: scholarly article
title: Recognition and isomorphism of tree-like \(P_4\)-connected graphs
zbMATH Open document ID: 0935.05077
DOI: 10.1016/S0166-218X(99)00140-7
author: Luitpold Babel
published in: Discrete Applied Mathematics
publication date: 2000-04-26T00:00:00Z
review text: The chordless path on four vertices is denoted by \(P_4\). A graph is \(P_4\)-connected if, for each partition of its vertices into two disjoint parts, there exists a \(P_4\) containing vertices from both parts. A \(p\)-tree is a \(P_4\)-connected graph in which each induced subgraph contains a vertex that belongs to at most one \(P_4\). Although a (\(P_4\)-connected) tree is, in general, not a \(p\)-tree, there are numerous tree-like characterizations of \(p\)-trees; see \textit{L. Babel} [Tree-like \(P_4\)-connected graphs, Discrete Math. 191, No. 1-3, 13-23 (1998)]. The author gives a new characterization of \(p\)-trees (Theorem 5.1) which allows him to recognize \(p\)-trees and to test isomorphism of \(p\)-trees in linear time.
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 1395018
zbMATH Keywords: \(P_4\)-structure
zbMATH Keywords: \(p\)-connected graphs
zbMATH Keywords: \(p\)-trees
zbMATH Keywords: recognition
zbMATH Keywords: isomorphism
MaRDI profile type: Publication
cites work: Tree-like \(P_4\)-connected graphs
cites work: Triangulating graphs with few \(P_4\)'s
cites work: Q4373667
cites work: On the structure of graphs with few \(P_4\)s
cites work: Q3097395
cites work: Complement reducible graphs
cites work: A Linear Recognition Algorithm for Cographs
cites work: Q4954442
cites work: Weakly triangulated graphs
cites work: Hamiltonicity in graphs with few \(P_ 4\)'s
cites work: P4-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
cites work: Q3355252
cites work: On a unique tree representation for \(P_ 4\)-extendible graphs
cites work: A tree representation for \(P_ 4\)-sparse graphs
cites work: Recognizing $P_4 $-Sparse Graphs in Linear Time
cites work: P-Components and the Homogeneous Decomposition of Graphs
cites work: Linear time optimization algorithms for \(P_ 4\)-sparse graphs
cites work: Q3128916
description: scientific article; zbMATH DE number 1395018