Colouring and list-colouring

Staying close in theme to last month’s post, this month I’m writing about decomposing matroids into independent sets.

The colouring number (or covering number), $\text{col}(M)$ of a matroid $M$ is defined as the smallest $t$ for which the ground set of $M$ can be partitioned into $t$ independent sets. I’ve written before about how I like the term colouring number since it highlights the analogy with the chromatic number of graphs (which is the smallest number of vertex-independent sets in which the graph can be partitioned). For this blog post, though, it is more illuminating to compare the colouring number to the edge-chromatic number of a graph.

The chromatic number for graphs has many variations that are studied for their own sake, such as the list-chromatic number. Similarly, there is a list-colouring version of the colouring number, which is defined as follows.

Definition. Let $M$ be a loopless matroid, and suppose that for each element $e$ of $M$ we are given a list $L(e)$ of colours available to element $e$. An $L$-colouring of $M$ is a function $c$ that maps each element $e$ of $M$ to an element of $L(e)$, with the additional property that $c^{-1}(i)$ is an independent set of $M$ for all $i \in \bigcup_{e} L(e)$. The matroid $M$ is $k$-list-colourable if it has an $L$-colouring whenever $|L(e)| \ge k$ for each $e$. We write $\text{col}_\ell(M)$ for the smallest $k$ such that $M$ is $k$-list-colourable.

When $L(e) = \{1,2,\ldots,k\}$ for each $e$, $L$-colouring corresponds to colouring the matroid with $k$ colours. This implies that $\text{col}_\ell(M) \ge \text{col}(M)$. For graphs the gap between chromatic number and list-chromatic number can be arbitrarily large. Surprisingly, the colouring and list-colouring numbers for matroids are equal, as shown by Seymour (using an application of matroid union!).

Theorem (Seymour). $\text{col}_\ell(M) = \text{col}(M)$ for all loopless matroids $M$.

It is clear from this theorem that nothing is to be gained by considering the list-colouring problem for matroids instead of the colouring problem.

However, it is not known if an analogue of Seymour’s result holds for matroid intersections. Let $M_1$ and $M_2$ be two matroids on a common ground set $E$. The colouring number $\text{col}(M_1 \wedge M_2)$ is the smallest $t$ for which $E$ can be partitioned into $k$ sets that are independent in both $M_1$ and $M_2$ (here, $M_1 \wedge m_2$ refers to the matroid intersection of $M_1$ and $M_2$). The list-colouring number for $\chi_\ell(M_1 \wedge M_2)$ is similarly obtained as a generalisation of the list-colouring number for matroids.

As in the case of (list-)colouring matroids, a straightforward argument shows that $\text{col}_\ell(M_1 \wedge M_2) \ge \text{col}(M_1 \wedge M_2)$, but it is not known if equality holds for all matroid intersections.

1-partition matroids and Galvin’s theorem

A 1-partition matroid is a matroid whose ground set can be partitioned into subsets such that the independent sets of the matroid contain at most one element from each of the subsets. In other words, a loopless matroid $M$ is a 1-partition matroid if and only if it is the direct sum of $r(M)$ parallel classes.

Such matroids arise naturally in matching theory. A bipartite graph $G$ with bipartition $L \cup R$ comes with two 1-partition matroids on $E$: one in which the parallel classes are formed by the edges incident with each of the vertices in $L$, and one whose parallel classes similarly correspond to the vertices in $R$. In fact, the matchings of $G$ are precisely the common independent sets of these two matroids.

Galvin showed that the list-edge-chromatic number and the edge-chromatic number of bipartite graphs coincide, which is equivalent to the following result.

Theorem (Galvin). $\text{col}_\ell(M_1 \wedge M_2) = \text{col}(M_1 \wedge M_2)$ for all loopless 1-partition matroids.

It is natural to ask if the conclusion of the theorem still holds when the 1-partition matroids are replaced by matroids that are the direct sum of uniform matroids whose rank may be larger than 1 (such matroids are called partition matroids). It turns out that the answer is ‘yes’, a result that was proved only a few months ago by Guo.

Theorem (Guo). $\text{col}_\ell(M_1 \wedge M_2) = \text{col}(M_1 \wedge M_2)$ for all loopless partition matroids.

When is $\text{col}_\ell(M_1 \wedge M_2) = \text{col}(M_1 \wedge M_2)$?

In light of Seymour’s theorem for the list-colouring number of matroids and the above results by Galvin and Guo, it is tempting to ask whether the list-colouring number is always equal to the colouring number for matroid intersections – as Király did.

Question (Király). Is it always true that $\text{col}_\ell(M_1 \wedge M_2) = \text{col}(M_1 \wedge M_2)$?

Very little appears to be known about this problem, with the exception of the results by Galvin and Guo and the following result by Király and Pap.

Theorem (Király and Pap). $\text{col}_\ell(M_1 \wedge M_2) = \text{col}(M_1 \wedge M_2)$ in each of the following cases:

• $M_1$ and $M_2$ are both transversal matroids; or
• $M_1$ is the graphic matroid and $M_2$ is the 1-partition matroid whose parts are formed by the in-stars of the graph that is the union of two arborescences with the same root; or
• $M_1$ and $M_2$ both have rank 2.

(The third case of of their result actually extends to the situation where $M_1$ is a rank-2 matroid and $M_2$ is an arbitrary matroid.)

As a step towards resolution of Király’s question, the following problem may be more accessible:

Question. Is it true that $\text{col}_\ell(M_1 \wedge M_2) = \text{col}(M_1 \wedge M_2)$ for all loopless rank-3 matroids $M_1$ and $M_2$?