Isomorphism of chordal (6, 3) graphs (Q1893148): Difference between revisions

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.