NDMI037 Geometric representations of graphs I - 2025/26

Monday 14:00 - S6

Sept 29, 2025
Introduction of the graphs classes we will see during the lecture
Chordal graphs
Definitions: chordal graphs, simplicial vertices, perfect elimination scheme (PES), clique-tree decomposition
Lemmas: every minimal vertex cut in a chordal graph induces a complete subgraph, every chordal graph is either complete or contains two non-adjacent simplicial vertices
Theorem: The following statements are equivalent for every graph G

G is chordal
G has a PES
G has a clique-tree decomposition
G is isomorphic to the intersection graph of a collection of subtrees of a tree.

M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Elsevier, 2004
See also handout No. 1 from 2021 in SIS