Isomorphism of chordal (6, 3) graphs
type: Item
instance of: scholarly article
title: Isomorphism of chordal (6, 3) graphs
zbMATH Open document ID: 0823.05043
DOI: 10.1007/BF02238229
author: Luitpold Babel
published in: Computing
publication date: 1995-10-08T00:00:00Z
review text: Let \(G= (V, E)\) be a graph with \(| V|= n\) and \(| E|= m\). \(V= S_ 1\cup S_ 2\cup\cdots \cup S_ q\) be a partition \(\mathcal T\) of the vertex set \(V\). Then \(\mathcal T\) is said to be simplicial if for \(1\leq i\leq q\) the vertices in \(S_ i\) are simplicial (have complete neighbourhoods) in \(G(S_ i\cup S_{i+ 1}\cup\cdots\cup S_ q)\), and \(\mathcal T\) is said to be regular if every vertex in a cell \(S_ i\) has the same number of neighbours in any cell \(S_ j\) (\(j= i\) included). Starting with the well-known perfect elimination scheme for a chordal graph the author constructs its coarsest simplicial partition in \(\mathcal T\) in \(O(n+ m)\) time and refines it to a regular partition in \(O(m\log n)\) time, thus obtaining the coarsest regular simplicial partition in \(O(n+ m\log n)\) time. A graph is called a \((q, t)\) graph if no set of at most \(q\) vertices induces more than \(t\text{ P}_ 4\text{s}\). The author introduces a generalized definition of stars and spiders (with thin or thick legs) and mentions a forbidden subgraph characterization of (6, 3) graphs. Using these he proves that the automorphism partition of chordal (6, 3) graphs coincides with its coarsest regular simplicial partition and deduces that isomorphism of such graphs can be described in \(O(n+ m\log n)\) time.
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 769255
zbMATH Keywords: perfect elimination scheme
zbMATH Keywords: chordal graph
zbMATH Keywords: coarsest simplicial partition
zbMATH Keywords: regular partition
zbMATH Keywords: stars
zbMATH Keywords: spiders
zbMATH Keywords: forbidden subgraph characterization
zbMATH Keywords: automorphism partition
zbMATH Keywords: isomorphism
MaRDI profile type: Publication
cites work: Q4091421
cites work: A Linear Time Algorithm for Deciding Interval Graph Isomorphism
cites work: Complement reducible graphs
cites work: On testing isomorphism of permutation graphs
cites work: Q4120604
cites work: Q3328583
cites work: Q4148000
cites work: Q3875946
cites work: P4-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
cites work: A New Class of Brittle Graphs
cites work: A tree representation for \(P_ 4\)-sparse graphs
cites work: Isomorphism Testing in Hookup Classes
cites work: Q4130999
cites work: Isomorphism of graphs of bounded valence can be tested in polynomial time
cites work: Graph isomorphism and theorems of Birkhoff type
cites work: Strong tree-cographs are Birkhoff graphs
cites work: A note on compact graphs
full work available at URL: https://doi.org/10.1007/bf02238229
OpenAlex ID: W1559316566
description: scientific article; zbMATH DE number 769255