Kurt Gödel Research Center

2016 seminar talk: Some graph theory from the Rockies

Talk held by Daniel Soukup (KGRC) at the KGRC seminar on 2016-10-13.

Abstract

The goal of this talk is to describe two projects I have been involved with at the University of Calgary in the last 8 months. First, we will look at the problem of finding independent partial transversals in sparse infinite graphs: we show that if $G$ is an infinite $K_n$-free graph and $m$ is finite then there is a finite $r=r(G,m)$ so that whenever the vertices of $G$ are partitioned into $r$ sets of equal size then there is an independent set $A$ which meets at least $m$ classes in a set of size of $G$. We determine the exact value of $r(G,m)$ for a few examples, in particular for Henson's homogeneous, universal $K_n$-free graphs. Joint work with C. Laflamme, A. A. Lopez, and R. Woodrow.

Second, we look at the following conjecture of S. Thomasse: for any digraph $D$, there is an appropriate set $C$ of cycles so that after reversing the orientation along members of $C$ the resulting digraph can be covered by two acyclic vertex sets. We will summarize the current knowledge on this question in the finite and infinite case. Joint work with C. Laflamme and A. A. Lopez.