### General Information

Student: |
Jan Vobornik |

Office: |
442 |

School: |
Charles University in Prague |

E-mail: |
janv guess_what_is_here reu.dimacs.rutgers.edu |

Projects: |
Subclasses of Chordal Graphs |

### Subclasses of Chordal Graphs

#### Project Description

For a fixed tree $T$, denote the class of all intersection graphs of subtrees of $T$ by $T\!-\!GRAPH$.
We obtain an infinite hierarchy between $INT$ and $CHOR$, since
$$INT \subseteq T\!-\!GRAPH \subsetneq CHOR.$$

#### 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

### Presentations

### Additional Information

My Mentor