Macaulay2 » Documentation
Packages » EdgeIdeals :: isChordal
next | previous | forward | backward | up | index | toc

isChordal -- determines if a graph is chordal



A graph is chordal if the graph has no induced cycles of length 4 or more (triangles are allowed). To check if a graph is chordal, we use a characterization of Fr\"oberg (see "On Stanley-Reisner rings," Topics in algebra, Part 2 (Warsaw, 1988), 57-70, Banach Center Publ., 26, Part 2, PWN, Warsaw, 1990.) that says that a graph G is chordal if and only if the edge ideal of G^c has a linear resolution, where G^c is the complementary graph of G.

i1 : S = QQ[a..e];
i2 : C = cycle S;
i3 : isChordal C

o3 = false
i4 : D = graph {a*b,b*c,c*d,a*c};
i5 : isChordal D

o5 = true
i6 : E = completeGraph S;
i7 : isChordal E

o7 = true

Ways to use isChordal :

For the programmer

The object isChordal is a method function.