Tata Institute of Fundamental Research

An Introduction to Chordal Graphs And Clique Trees

STCS Student Seminar
Speaker: Vidya Sagar Sharma
Organiser: Sayantan Chakraborty
Date: Saturday, 30 Jan 2021, 17:15 to 18:15

(Scan to add to calendar)
Abstract:  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.
Reference: link.springer.com/content/pdf/10.1007%2F978-1-4613-8369-7_1.pdf

Zoom Link : https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09