An Introduction to Chordal Graphs And Clique Trees

Vidya Sagar Sharma
Sayantan Chakraborty
Saturday, 30 Jan 2021, 17:15 to 18:15
An undirected graph is chordal if every cycle of length greater than three has a chord: namely, an edge connecting two nonconsecutive vertices on the cycle.  A clique of a graph $G$ is any maximal set of vertices that is complete in $G$.  Let $G$ be a chordal graph and $K_G = \{ K_1, K_2, ..., K_m \}$  denotes the set containing the cliques of $G$, then a tree with vertex set $K_G$ is said to be a clique tree of the chordal graph $G$ if it follows the clique intersection property: For every pair of distinct cliques $K,K' \in K_G$, the set $K \cap K'$ is contained in every clique on the path connecting $K$ and $K'$ in the tree.

In this talk, we will see a few properties of the chordal graphs and the clique trees of the chordal graphs.

Zoom Link :