2014-10-06
11:00-12:00
FAMNIT-SEMIN
Dr. Pablo De Caria (National University of La Plata, Argentina)
On chordal and dually chordal graphs and their tree representations
Chordal and dually chordal graphs are well known classes, whose duality becomes evident by the use of trees: a dually chordal graph is characterized by the existence of a tree such that every clique of the graph induces a subtreee (the compatible tree), whereas a chordal graph is characterized by the existence of a tree such that each member of the dual of the clique family induces a subtree (the clique tree).
In this talk, clique trees and compatible trees are analyzed in more depth, thus strengthening the sense of duality between the two classes.
This work is mostly based on some chapters of my PhD thesis, under the supervision of Marisa Gutierrez.