# isChordal -- determines if a graph is chordal

## Synopsis

• Usage:
b = isChordal G
• Inputs:
• G, ,
• Outputs:
• b, , true if the graph is chordal

## Description

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 :

• "isChordal(Graph)"

## For the programmer

The object isChordal is .