PIMS-UVic Discrete Math Seminar: Alexander Clow

  • Date: 02/29/2024
  • Time: 10:00
Lecturer(s):
Alexander Clow, SFU
Location: 

Simon Fraser University

Topic: 

Oriented Colouring Graphs of Bounded Euler Genus

Description: 

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).

Other Information: 

Location: COR A128

Time: 10am PacificĀ