Monday, June 7, 3pm ET (8pm BST, 7am Tue NZST)
Abhinav Shantanam, Simon Fraser University
Pancyclicity in $4$-connected planar graphs

Abstract:
A graph on $n$ vertices is said to be pancyclic if, for each $k \in \{3,…,n\}$, it contains a cycle of length $k$. Following Bondy’s meta-conjecture that almost any nontrivial condition on a graph which implies Hamiltonicity also implies pancyclicity, Malkevitch conjectured that a $4$-regular, $4$-connected planar graph containing a $4$-cycle is pancyclic. We show that, for any edge $e$ in a $4$-connected planar graph $G$, there exist $\lambda(n-2)$ cycles of pairwise distinct lengths containing $e$, where $5/12 \leq \lambda \leq 2/3$. Joint work with Bojan Mohar.

Monday, May 31, 3pm ET (8pm BST, 7am Tue NZST)
Daniel Slilaty, Wright State University
Orientations of golden-mean matroids

Abstract:

Tutte proved that a binary matroid is representable over some field of characteristic other than 2 if and only if the matroid is regular. His result inspired the discovery of analogs for $GF(3)$-representable matroids by Whittle, $GF(4)$-representable matroids by Vertigan as well as Pendavingh and Van Zwam, and $GF(5)$-representable matroids by Pendavingh and Van Zwam.

Bland and Las Vergnas proved that a binary matroid’s orientations correspond to its regular representations. (Minty’s result on digraphoids is closely related.) Lee and Scobee proved that a $GF(3)$-representable matroid’s orientations correspond to its dyadic representations. In this talk we will explore orientations of $GF(4)$-representable matroids. A natural partial field to use is the golden-mean partial field; however, not every orientation of a $GF(4)$-representable matroid comes from a golden-mean representation. For example, $U_{3,6}$ has 372 orientations but only 12 of them come from golden-mean representations. We will give a combinatorial characterization of those orientations of $GF(4)$-representable matroids which do come from golden-mean representations and show that these orientations correspond one-to-one to the golden-mean representations.

Joint work with Jakayla Robbins.

Monday, May 17, 3pm ET (8pm BST, 7am Tue NZST)
Bertrand Guenin, University of Waterloo
Graphs with the same even cycles

Abstract:

Monday, May 10, 3pm ET (8pm BST, 7am Tue NZST)
Sophie Spirkl, University of Waterloo
The complexity of list-5-colouring H-free graphs

Abstract:

A $k$-list-assignment for a graph $G$ is a function $L$ from $V(G)$ to subsets of $\{1, …, k\}$. The list-$k$-colouring problem asks, given $G$ and a $k$-list-assignment $L$, is there a colouring $f$ of $G$ with $f(v)$ in $L(v)$ for all $v$ in $V(G)$? This generalizes the $k$-colouring problem (where we use $L(v) = \{1, …, k\}$ for every vertex).

For $k$ at least $3$, both $k$-colouring and list-$k$-colouring are NP-hard, which motivates studying the complexity of these problems when the input is restricted to $H$-free graphs (for a fixed $H$, excluded as an induced subgraph).

I will present an algorithm for list-$5$-colouring restricted to $H$-free graphs for all $H$ which consist of connected components each of which is a $3$-vertex path. This, together with previous results, gives a complete answer to the question, “for which $H$ is list-$5$-colouring restricted to $H$-free graphs NP-hard?”

Joint work with Sepehr Hajebi and Yanjia Li.