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.

Monday, April 19, 3pm ET (8pm BST, 7am Tue NZST)
Daniel Bernstein, MIT
Rigidity of symmetry-forced frameworks

Abstract:

The fundamental problem in rigidity theory is to determine whether a given immersion of a graph into $\mathbb{R}^d$ can be continuously deformed, treating the edges as rigid bars that can move freely about their incident vertices. Rigidity is a generic property of each fixed graph $G$, in the sense that almost all immersions of $G$ into $\mathbb{R}^d$ are rigid, or almost all immersions are flexible. The graphs that are generically rigid in $\mathbb{R}^d$ are the spanning sets of a certain matroid. The main result of my talk will be about rigidity in the plane when the graphs and their immersions have certain symmetry constraints.

Monday, April 12, 3pm ET (8pm BST, 7am Tue NZST)
Daryl Funk, Douglas College
The class of bicircular matroids has only a finite number of excluded minors

Abstract:

We show that the class of bicircular matroids has only a finite number of excluded minors. Key tools used in our proof include representations of matroids by biased graphs and the recently introduced class of quasi-graphic matroids. We show that if $N$ is an excluded minor of rank at least eight, then $N$ is quasi-graphic. Several small excluded minors are quasi-graphic. Using biased-graphic representations, we find that $N$ already contains one of these. We also provide an upper bound, in terms of rank, on the number of elements in an excluded minor, so the result follows.