CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Structural graph theory II
Org: Sophie Spirkl (Princeton University, USA)

MATT DEVOS, Simon Fraser University
Immersion of 2-Regular Digraphs  [PDF]

There is a wonderful theory of 2-regular digraphs involving special embeddings and immersion that parallels the well-known world of surface embeddings and minors for undirected graphs. I will describe some recent progress in this new setting including a finite obstruction theorem for embedding in an arbitrary surface, an analogue of Negami’s conjecture, and a counterexample to the analogue of the strong embedding conjecture. This is all joint work with my recently finished PhD student, Stefan Hannie.

BERNARD LIDICKÝ, Iowa State University
Coloring count cones of planar graphs  [PDF]

For a plane near-triangulation $G$ with the outer face bounded by a cycle $C$, let $n^\star_G$ denote the function that to each 4-coloring $\varphi$ of $C$ assigns the number of ways $\varphi$ extends to a 4-coloring of $G$. The block-count reducibility argument is equivalent to the statement that $n^\star_G$ belongs to a certain cone (depending only on the length of $C$). We investigate the properties of this cone for $|C| = 5$, formulate a conjecture strengthening the Four Color Theorem, and present evidence supporting this conjecture. This is a joint work with Zdeněk Dvořák.

ROSE MCCARTY, University of Waterloo
Decomposing a graph into odd trails  [PDF]

We give a precise characterization of when the edge set of a graph can be partitioned into $k$ odd trails that all begin and end at a vertex $v$. We discuss related results for group-labeled graphs and their connections to vertex minors. Joint work with Jim Geelen and Paul Wollan.

The Erdos-Hajnal property for graphs with no fixed cycle as a pivot-minor  [PDF]

We prove that for every integer $k$, there exists $\varepsilon>0$ such that every $n$-vertex graph with no pivot-minors isomorphic to $C_k$, the cycle graph on $k$ vertices, has a pair of disjoint sets $A$, $B$ of vertices such that $|A|, |B|\ge \varepsilon n$ and $A$ is complete or anticomplete to $B$. This proves the analog of the Erd\H{o}s-Hajnal conjecture for the class of graphs with no pivot-minors isomorphic to $C_k$. This is joint work with Jaehoon Kim.

A tale of two graph invariants  [PDF]

The cop number of a graph is the minimum number of cops needed to capture a robber where the cops and robber move along the edges of the graph. The cop number of a graph depends very heavily on the structure of the graph, but the precise dependence is not known. I will discuss how the cop number behaves in graph coloring theorems when it replaces the chromatic number. I will show that there exist triangle-free graphs with cop number 2 and chromatic number arbitrarily large. Several related results will also be presented.