General Information

---

Subclasses of Chordal Graphs

For a fixed tree $T$, denote the class of all topological intersection graphs of a tree $T$ by $T\!-\!\textrm{GRAPH}$. We obtain an infinite hierarchy between $\textrm{INT}$ and $\textrm{CHOR}$, since $$\textrm{INT} \subseteq T\!-\!\textrm{GRAPH} \subsetneq \textrm{CHOR}.$$ We study various structural and computational aspects of the class $T\!-\!\textrm{GRAPH}$.

---

Previous work

• The automorphism groups of interval graphs were recently characterized (P. Klavik, P. Zeman).
• The automorphism groups of chordal graphs are known to be universal (K. Booth, G. Lueker).

---

Weekly Log

Week 1:

We spent the first week by reading various articles and preparing the introductory presentation.

Week 2:

The most basic computational question for a class of graphs is the problem of determining whether a given graph belong to this class or not. This problem is called recognition. We started to work on a special case of recognition of $T\!-\!{\rm GRAPH}$s, more precisely recognition of $K_{1,3}\!-\!{\rm GRAPH}$s.
We managed to find a polynomial-time algorithm for recognizing $K_{1,3}\!-\!\textrm{GRAPH}$s.

Week 3:

In this week, we managed to find a polynomial-time algorithm for recognizing $T\!-\!\textrm{GRAPH}$s.

Week 4:

In this week we started to work on the problem of graph isomorphism of $T\!-\!\textrm{GRAPH}$s, which asks whether two $T\!-\!\textrm{GRAPH}$s on input are isomorphic. We got some insight into the problem, however, we got stuck on one case. We think that the graph isomorphism should be solvable in polynomial time on $T\!-\!GRAPH$s.

Week 5:

We started to study the problem of extending partial representations of $T\!-\!\textrm{GRAPH}$s. This is a generaliztion of the rocognition problem: some subtrees can be predrawn and the problem asks whether we can draw the rest. So far, we have only some partial results, however, we think the problem is solvable in polynomial time.

Week 6:

We managed to find an $XP$ algorithm for partial representation extension of $T\!-\!\textrm{GRAPH}$s.

Week 7:

We focused on characterisation of automorphism groups of $T\!-\!\textrm{GRAPH}$s and got some basic partial results. We also did the final presentation.

---

Coworkers

• Jan Vobornik
• Martin Topfer

---

Presentations

• First Presentation (Introduction)

---

My Mentor

Professor James Abello
    http://www.mgvis.com/
    http://www.mgvis.com/AbelloVitaResearchOct08.html