PIMS-UVic Discrete Math Seminar: Alexander Clow

In this talk we consider the oriented colouring problem for graphs with bounded Euler genus. That is we consider the smallest $k$ such that all oriented graphs embeddable on surfaces of Euler genus at most $g$ necessarily have an oriented homomorphism to a graph of order $k$. For convenience given a fixed $g$ and $k$, we let $\chi_o(g) = k$. We will discuss our proofs that $\Omega((\frac{g^2}{\log{g}})^{\frac{1}{3}}) \leq \chi_o(g) \leq (1+o(1))g^{6400}$, which improves the prior upper bound of order $2^{O(g^{\frac{1}{2}+o(1)})}$ and lower bound of order $\Omega(\sqrt{g})$, as well as exploring how our bounds might be improved in future work.

Joint work with Peter Bradshaw (University of Illinois Urbana Champaign), and Jingwei Xu (University of Illinois Urbana Champaign).