Research
Recently, myself, Bruce Reed and Hehui Wu solved Ohba's Conjecture on list colouring. The purpose of this page is to explain some of the key ideas of our proof, which may be useful for tackling related problems in the future.
The problem is the following:
Ohba's Conjecture. If $|V(G)|\leq 2\chi(G)+1$, then $\chi_\ell(G)=\chi(G)$.
The first observation is that Ohba's Conjecture is true if and only if it is true for complete multipartite graphs. That is, if $G$ is a counterexample to Ohba's Conjecture, then by adding edges between any two colour classes of a $\chi(G)$-colouring of $G$, one can obtain a complete $\chi(G)$-partite counterexample.
For more background on the problem, click here. For a detailed proof of the conjecture, see the .pdf of our manuscript.
1. Hall's Theorem
The first application of Hall's Theorem to list colouring dates back to the original paper of Erdős, Rubin and Taylor (1979). Ohba's Conjecture itself seems to have been partially motivated by the following result, which proves a special case. We reproduce their proof because it is sweet.
Theorem 1 (Erdős, Rubin and Taylor (1979)). If $G$ is the complete $k$-partite graph with all parts having size $2$, then $\chi_\ell(G)=k$.
Proof. We proceed by induction on $k$, where the case for $k=1$ is trivial. Let $L$ be any assignment of lists of size $k$ to the vertices of $G$. If there is a part $\{u,v\}$ of $G$ which satisfies $L(u)\cap L(v)\neq \emptyset$, then we simply colour $u$ and $v$ with a colour $c\in L(u)\cap L(v)$ and delete $c$ from the list of any remaining vertex. By the inductive hypothesis, there is an acceptable colouring of $G-\{u,v\}$, and so we are done in this case.
Thus, we assume that $L(u)\cap L(v)=\emptyset$ for every part $\{u,v\}$ of $G$, which implies that $|L(u)\cup L(v)|\geq 2k$. In this case, we use Hall's Theorem to show that there is a system of distinct representatives for $\{L(v): v\in V(G)\}$. Indeed, for any set $S$ of at most $r$ vertices, we have $$|\cup_{v\in S}L(v)|\geq k\geq |S|.$$ Also, any set $S$ of more than $r$ vertices must contain both vertices of some part $\{u,v\}$ of $G$. Since $|L(u)\cup L(v)|\geq 2k$ and $|S|\leq |V(G)|\leq 2k$, we have $$|\cup_{v\in S}L(v)|\geq 2k \geq |S|.$$ Thus, we can colour the vertices of $G$ with a system of distinct representatives for $\{L(v):v\in V(G)\}$. Clearly this is an acceptable colouring since every colour appears on at most one vertex. QED
Sweet, isn't it? I told you it would be!
2. More Hall's Theorem
Later, it was independently observed by Kierstead (2000) and Reed and Sudakov (2005) that Erdős et al.'s trick of using Hall's Theorem can give useful information for more general problems.
The best way to visualize the next result is in terms of a bipartite auxiliary graph. Given a $k$-list assignment $L$ of $G$, let $C:=\cup_{v\in V(G)}L(v)$ and let $B$ be the bipartite graph with bipartition $(V(G),C)$ where each vertex $v\in V(G)$ is joined to precisely the colours in $L(v)$. Now, of course, a matching in $B$ that saturates $V(G)$ would give us a system of distinct representatives for $\{L(v): v\in V(G)\}$ and hence an acceptable colouring, as in Theorem 1.
But, what about a matching that saturates $C$? As it turns out, we can always assume that such a matching exists.
Lemma 2 (Kierstead (2000), Reed and Sudakov (2005)). If $G$ is not $k$-choosable, then there is a $k$-list assignment $L$ of $G$ such that:
(a) there is a matching in $B$ that saturates $C$, and
(b) there is no acceptable colouring.
Proof. Let $L$ be a $k$-list assignment of $G$ so that $G$ is not $L$-colourable and, subject to this, $|C|$ is minimized. We show that there is indeed a matching in $B$ which saturates $C$.
If no such matching exists, then by Hall's Theorem there is a set $S$ of colours such that $|N_B(S)|<|S|$. Subject to this, let $|S|$ be minimum. Now, by minimality of $|S|$, we see that for any $c\in S$ there is a matching $M$ in $B$ which saturates the set $T:=S-c$ of colours. It is easy to see that $M$ also saturates $N_B(S)=N_B(T)$ as well by combining the inequalities $|T|=|S|-1$ and $|N_B(S)|<|S|$. Therefore, we must have that $N_B(S)\neq V(G)$; otherwise, such a matching would indicate an acceptable colouring for $G$. Thus, let $w\in V(G)-N_B(S)$ be arbtrary. We define a new list assignment $L'$ by $L'(v)=L(v)$ if $v\notin N_B(S)$ and $L(v) = L(w)$ otherwise.
We observe that $L'(v)\cap S=\emptyset$ for all $v\in V(G)$ since every vertex of $N_B(S)$ changed its list to the list of a vertex outside of $N_B(S)$. Thus, we have $|\cup_{v\in V(G)}L'(v)|<|C|$. By our choice of $L$, this implies that there is an acceptable colouring $f'$ for $L'$. Now, we can construct an acceptable colouring $f$ for $L$ by letting $f=f'$ on $G-N_B(S)$ and colouring each vertex of $N_B(S)$ with the colour (in $T$) that it is matched to under $M$. This contradicts the assumption that there is no acceptable colouring for $L$. This contradicts the fact the $G$ is not $L$-colourable. QED
This lemma yields the following corollary, which is of independent interest.
Corollary 3 (Kierstead (2000), Reed and Sudakov (2005)). If $G$ is not $k$-choosable, then there is a $k$-list assignment $L$ of $G$ such that:
(a) $|\cup_{v\in V(G)} L(v)| < |V(G)|$, and
(b) there is no acceptable colouring.
In particular, this corollary is very useful when $|V(G)|$ is bounded, as is the case in Ohba's Conjecture.
Corollary 4 (Reed and Sudakov (2005)). If Ohba's Conjecture is false, then there is a counterexample which satisfies $|C| < |V(G)|\leq 2k+1$.
3. Adding Colours to the Lists (and Even More Hall's Theorem)
In this section, suppose that $G$ is a counterexample to Ohba's Conjecture; ie. $G$ is a complete $k$-partite graph on at most $2k+1$ vertices such that $\chi_\ell(G)>k$.
A breakthrough of our research is based on a simple question: What happens if we add a colour to one of the lists? Well, if you add enough colours in the right places, then eventually it becomes possible to find an acceptable colouring. So, then, what can be said about a so-called maximal list assignment? Ie. a list assignment $L$ such that
(1) $|L(v)|\geq k$ for all $v$,
(2) there is no acceptable colouring, and
(3) for all $v$, if a colour $c\notin L(v)$ is added to $L(v)$, then there is an acceptable colouring.
Now, the neat thing here is that if we add a colour $c\notin L(v)$ to $L(v)$, we immediately get a colouring $f$ that is acceptable on $G-v$ and satisfies $f(v)=c$ (otherwise it would be acceptable for $L$!). As it turns out, this infomation is sometimes useful for modifying $f$ to give us an acceptable colouring for $L$. In particular, this can be useful if $c$ appears in the list of many vertices.
Definition. Say that a colour $c$ is frequent if it appears in the lists of at least $k+1$ vertices.
We prove the following:
Lemma 5 (N., Reed, Wu (2012)). If $c$ is a frequent colour, then for every part $P$ of $G$ there is a vertex $v\in P$ with $c\in L(v)$.
Proof. Otherwise, let $v\in P$ be arbitrary and add the colour $c$ to $L(v)$. Then we obtain a colouring $f$ of $G$ which is acceptable on $G-v$ and has $f(v)=c$. Moreover, since no other vertex of $P$ has a list containing $c$, we must have $f^{-1}(c)=\{v\}$.
Now, our objective is to construct an acceptable colouring $f'$ of $G$ which has the same colour classes as $f$. To do so, we analyze a bipartite auxiliary graph. Let $$V_f:=\{f^{-1}(c'): c'\in f(V(G))\}$$ denote the set of all such colour classes. We define $B_f$ to be the bipartite graph with bipartition $(V_f,C)$ where each colour class $f^{-1}(c')\in V_f$ is joined to the colours of $\cap_{w\in f^{-1}(c')}L(w)$.
Observe that if there is a matching $M$ in $B_f$ saturating $V_f$, then there is an acceptable colouring $f'$ of $G$ with the same colour classes as $f$. That is, $f'$ is simply the colouring which assigns each colour class to the colour that it is matched to under $M$.
Therefore, by Hall's Theorem, there is a set $S\subseteq V_f$ such that $|N_{B_f}(S)| < |S|$. For every colour $c'\neq c$, we have that $f^{-1}(c')$ is joined to $c'$ in $B_f$ since $f$ is acceptable on $G-v$. Therefore, we must have $\{v\}\in S$ and $c\notin N_{B_f}(S)$.
Now, since $\{v\} \in S$, we have $$|S|>|N_{B_f}(S)|\geq |L(v)|\geq k.$$ However, every colour class in $S$ must contain a vertex $w$ such that $c\notin L(w)$. Since $c$ is frequent, we must have $$|S|\leq |V(G)| -(k+1)\leq (2k+1)-(k+1)=k.$$ But this is a contradiction, since we already showed that $|S|>k$! The result follows. QED
Notice that this proof only required that $f(v)$ is frequent and $f^{-1}(f(v))=\{v\}$. In fact, the proof does not require $v$ to be the unique such vertex. This suggests the following definition and lemma.
Definition. Say that a proper colouring $f:V(G)\to C$ is near-acceptable if for every $v\in V(G)$ either
(a) $f(v)\in L(v)$ or
(b) $f(v)$ is frequent and $f^{-1}(f(v))=\{v\}$.
Lemma 6 (N., Reed, Wu (2012)). If there is a near-acceptable colouring of $G$, then there is an acceptable colouring of $G$.
We should mention another crucial idea in our proof. In the proof of Lemma 5, suppose instead that $c$ is a colour that is in the list of many singleton parts of $G$. Then, none of these singleton parts are contained in $S$. Therefore, if we colour a set $A\supseteq V(G)-S$, then the remaining graph $G-A$ has a chromatic number that is much smaller than $k$ (since $A$ contains many singleton parts). If this colouring does not use too many colours of $N_{B_f}(S)$, then we can colour $G-A$ by the induction hypothesis. For a more rigorous argument, see Section 2 of the manuscript.
The other parts of the proof (ie. the parts which are NOT based on Hall's Theorem) include the proofs of the following Lemmas which, together with Lemma 6, complete the proof of Ohba's Conjecture.
Lemma 7 (N., Reed, Wu). If there are at least $k$ frequent colours, then there is a near-acceptable colouring.
Lemma 8 (N., Reed, Wu). If Ohba's Conjecture is false, then there is a counterexample with at least $k$ frequent colours.
The proof of Lemma 7 includes an explicit construction via a greedy procedure. The proof heavily exploits the fact that, in a near-acceptable colouring, a frequent colour $c$ can be used on a vertex $v$ for which $c\notin L(v)$, provided that $f^{-1}(c) = \{v\}$. For a proof of Lemma 7, see Section 3 of our manuscript.
To prove Lemma 8, we consider a minimal counterexample to Ohba's Conjecture and use the notion, hinted at the end of the previous section, of a colour which is `frequent among singletons,' along with some clever counting arguments. For a proof of Lemma 8, see Section 4 of our manuscript.
In conclusion, we remark that our proof can be boiled down to (1) a few applications of Hall's Theorem, (2) a greedy colouring procedure, and (3) a bit of clever counting. Perhaps, by following a similar formula, other results on list colouring can be proven. Specifically, it may be possible to prove more results about graphs with a bounded number of vertices.
Consider, for example, a problem of Erdős, Rubin and Taylor (1979):
Question: For all $m$ and $k$, what is the list chromatic number of the complete $k$-partite graph with all parts of size $m$?
Theorem 1 asserts that for $m=2$ the answer is $k$. The result of Kierstead (2000) is that the answer is $ceil((4k-1)/3)$ when $m=3$. However, it seems that no other values are known.
Another interesting problem could be to bound the list chromatic number of all complete $k$-partite graphs on at most $f(k)$ for some function $f$ which is larger than $2k+1$. Or, perhaps, to characterize all complete $k$-partite graphs $G$ on at most $f(k)$ vertices which satisfy $\chi_\ell(G)=k$. In particular, it seems reasonable to expect that the case $f(k)=2k+2$ could be settled by tightening some of our arguments.
Research Topics: Ohba's Conjecture Circular Colouring the Real Orthogonality Graph Graph Homotopy Extending Colourings Mixing Circular Colourings