ISOMORPHISM OF CHORDAL (6,3) GRAPHS

A graph is chordal if it contains no chordless cycles of length at least four and (q, t) if no set of at most q vertices induces more than t paths of length three. It is known that the isomorphism problem is isomorphism complete for chordal graphs and for (6,3) graphs. We present polynomial methods to determine the automorphism partition and to test isomorphism of graphs which are both chordal and (6,3). The approach is based on the study of simplicial partitions of chordal graphs. It is proved that for chordal (6,3) graphs the automorphism partition coincides with the coarsest regular simplicial partition. This yields an O(n+m log n) isomorphism test.