Question:The labeling problem of elimination sequences in chordal graph testing.

Question:The labeling problem of elimination sequences in chordal graph testing.

Maple 2023

A chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. A perfect elimination ordering in a graph is an ordering of the vertices of the graph such that, for each vertex v, v and the neighbors of v that occur after v in the order form a clique.  A graph is chordal if and only if it has a perfect elimination ordering.

I  use `IsChordal`  to test whether the lexicographic product of  two graphs g1,g2 is a chordal graph. It returned true and provided a perfect elimination sequence `1, 2, ..., 30`. However, vertices of `s`  are `"1:1", "1:2", ..., "10:3"`, rather than using Arabic numerals. Therefore, it is difficult for me to extract useful information from the perfect elimination sequence.

 > with(GraphTheory): g1:=PathGraph(10): g2:=CycleGraph(3):
 > s:=LexicographicProduct(g1,g2):
 > IsChordal(s,eliminationordering=true)
 (1)
 > DrawGraph(s)
 > Vertices(s)
 (2)