Atlantic Graph Theory Seminar

Two short talks by grad students Alex Clow and William Kellough. ‘Live’ viewing in Chase 227 for those at Dalhousie.

Talk 1:
Alex Clow, Simon Fraser University
Polynomially Bounding the Oriented Chromatic Number in Euler Genus

In this talk we consider the oriented chromatic number of graphs with bounded Euler genus. In particular, we present our proofs that the oriented chromatic number is at most $g^{6400}$ for sufficiently large $g$ and at least $\Omega((\frac{g^2}{\log g})^{1/3})$. This is a major improvement over the previous best upper bound which is exponential in genus. We conclude the talk by discussing directions for future study. Joint work with Peter Bradshaw and Jingwei Xu from the University of Illinois at Urbana Champaign.

Talk 2:
William Kellough, Memorial University
How to Catch a Cheating Robber on Strong Products

Cops and Robbers is a pursuit-evasion game played on the vertices of a graph. One player controls a set of cops and the other player controls a robber. The cops win if a cop can move to the vertex occupied by the robber in finitely many turns, otherwise the robber wins. In this talk, we consider a variation of Cops and Robbers where both players move simultaneously and the robber “cheats” by knowing how the cops will move each round. We will give bounds on the minimum number of cops needed to win this game when played on the strong product of two graphs. This is joint work with Nancy Clarke and Danny Dyer.

Join Zoom Meeting
https://us02web.zoom.us/j/86415230827?pwd=QUxLUnlMdWYzL05zSUJ4bnBCOUJnZz09