2024 CMS Winter Meeting
Vancouver/Richmond, Nov 29 - Dec 2, 2024
Graph Coloring, Minors, and Hypergraphs (previously Graph Theory)
Org: Alexander Clow, Bojan Mohar and Ladislav Stacho (Simon Fraser University)
[PDF]
Org: Alexander Clow, Bojan Mohar and Ladislav Stacho (Simon Fraser University)
[PDF]
- ALEXANDER CLOW, Simon Fraser University
A Map Colour Theorem for Oriented Colouring [PDF]
-
A classical problem in graph colouring theory, dating back to Heawood, is to study the number of colours required to colour graphs embeddable on a surface of bounded Euler genus. In this talk we will present a nearly tight bound on the oriented chromatic number in terms of the Euler genus of the graph being coloured. In particular, we will show that there exists oriented graphs with Euler genus at most $g$ that require $\Omega(\frac{g}{\log(g)})$-colours in any oriented colouring, before proving that every oriented graph with Euler genus at most $g$ has an oriented colouring using at most $O(g\log(g))$-colours.
- GENA HAHN, UMontreal
- PENNY HAXELL, Waterloo
- EMILY HEATH, Cal Poly Pomona
- JEANNETTE JANSSEN, Dalhousie
- ANDREW LANE, UVic
- BEN MOORE, ISTA
- JOSHUA NEVIN, University of Ottawa
Distant 2-Colored Components on Embeddings [PDF]
- PENNY HAXELL, Waterloo
-
In this talk, we present a new result which consists of the following generalization of Thomassen's 5-choosability theorem: Let $G$ be a finite graph embedded on a surface of genus $g$. Then $G$ can be $L$-colored, where $L$ is a list-assignment for $G$ in which every vertex has a 5-list except for a collection of pairwise far-apart components, each precolored with an ordinary 2-coloring, as long as the face-width of $G$ is $2^{\Omega(g)}$ and the precolored components are of distance $2^{\Omega(g)}$ apart. This provides an affirmative answer to a generalized version of a conjecture of Thomassen and also generalizes a result from 2017 of Dvo\v{r}\'ak, Lidick\'y, Mohar, and Postle about distant precolored vertices.
- JOZSEF SOLYMOSI, UBC