On the structure of graphs with few \(P_4\)s
type: Item
instance of: scholarly article
title: On the structure of graphs with few \(P_4\)s
zbMATH Open document ID: 0908.05065
DOI: 10.1016/S0166-218X(97)90120-7
author: Luitpold Babel
author: Stephan Olariu
published in: Discrete Applied Mathematics
publication date: 1998-10-18T00:00:00Z
full work available at URL: dam
review text: This paper deals with the \(P_4\) structure of graphs (\(P_4\) denotes a path of length 3). A \((q,t)\) graph is one in which no set of \(q\) or fewer vertices induces more than \(t\) distinct \(P_4\)'s. The main result of this paper is that \((q,q-4)\) graphs form a class of graphs for which the isomorphism problem can be solved in polynomial time. The authors show that \((q,q-4)\) graphs can be encoded as rooted trees whose internal nodes represent certain graph operations and whose leaves correspond to certain basic graphs. As a result of this tree encoding isomorphism tests between \((q,q-4)\) graphs can be done in polynomial time. Another interesting result proved is that all \((q,q-4)\) graphs with \(4\leq q\leq 8\) are brittle. A graph \(G\) is brittle if each induced subgraph \(H\) of \(G\) contains a vertex which is either not the endpoint or not the midpoint of any \(P_4\) in \(H\). The graphs in this class are distinct from all previously known brittle graphs.
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1180349
zbMATH Keywords: \(P_4\)
zbMATH Keywords: cograph
zbMATH Keywords: brittle
zbMATH Keywords: isomorphism problem
reviewed by: Robert R. Molina
MaRDI profile type: Publication
cites work: Q4773298
cites work: The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
cites work: A Linear Time Algorithm for Deciding Interval Graph Isomorphism
cites work: Q3347930
cites work: Complement reducible graphs
cites work: A Linear Recognition Algorithm for Cographs
cites work: Q3328583
cites work: P-Components and the Homogeneous Decomposition of Graphs
cites work: A tree representation for \(P_ 4\)-sparse graphs
cites work: Recognizing $P_4 $-Sparse Graphs in Linear Time
cites work: P4-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
cites work: On a unique tree representation for \(P_ 4\)-extendible graphs
cites work: A New Class of Brittle Graphs
cites work: Isomorphism Testing in Hookup Classes
cites work: Q4130999
description: scientific article; zbMATH DE number 1180349