Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 ChordalGraphQ

Source Notebook

Test whether a graph is chordal

Contributed by: Jon McLoone

ResourceFunction["ChordalGraphQ"][gr]

test whether the graph gr is chordal.

Details

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.

Examples

Basic Examples (3) 

Complete graphs are chordal:

In[1]:=
gr = CompleteGraph[4]
Out[1]=
In[2]:=
ResourceFunction["ChordalGraphQ"][gr]
Out[2]=

The HouseX graph is chordal:

In[3]:=
gr = GraphData["HouseXGraph"]
Out[3]=
In[4]:=
ResourceFunction["ChordalGraphQ"][gr]
Out[4]=

But the house graph is not:

In[5]:=
gr = GraphData["HouseGraph"]
Out[5]=
In[6]:=
ResourceFunction["ChordalGraphQ"][gr]
Out[6]=

This simple cycle is not chordal:

In[7]:=
gr = Graph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 4, 4 \[UndirectedEdge] 1}]
Out[7]=
In[8]:=
ResourceFunction["ChordalGraphQ"][gr]
Out[8]=

Publisher

Jon McLoone

Version History

  • 1.0.0 – 25 March 2022

Related Resources

License Information