Research
Extending Colourings:
Thomassen posed the following question in 1997: Given a planar graph $G$ and a partial colouring $f$ of a set $P\subseteq V(G)$ using at most $5$ colours, can $f$ be extended to a $5$-colouring of $G$ provided that the distance between any two vertices of $P$ is at least $100$?
In 1998, Albertson gave an elegant and simple proof of Thomassen's Conjecture. In fact, he shows that a distance of $4$ between precoloured vertices suffices and that this is best possible.
Theorem (Albertson, 1998): If $G$ is a planar graph and $P\subseteq V(G)$ such that the distance between any two vertices in $P$ is at least $4$, then any $5$-colouring of $P$ extends to a $5$-colouring of $G$.
Proof. Let $f$ be any $5$-colouring of $P$ using colours $\{1,2,3,4,5\}$. By the Four Colour Theorem, there exists a proper colouring of $G$ from colours $\{1,2,3,4\}$. The goal is to alter $g$ to agree with $f$ on $P$, while only using colours from $\{1,2,3,4,5\}$.
Given a vertex $v\in P$, if $g(v)=f(v)$, then there is nothing to prove. So, suppose $c=f(v)\neq g(v)$ and recolour $v$ to $c$. If this causes problems, then it is because there is a neighbour $u$ of $v$ so that $g(u)=c$. However, we may simply recolour $u$ to the colour $5$. Since any two vertices of $P$ are at at least distance $4$ from one another, there can be no conflict between vertices that receive colour $5$. The result follows.
QED
Notice that the hypothesis that $G$ is planar was only used to obtain a $4$-colouring of $G$. Moreover, nothing in this proof is particularly specific to $5$-colourings. In fact, the same proof can be used to establish the following.
Theorem (Albertson 1998): If $G$ is a $k$-colourable graph and $P\subseteq V(G)$ such that the distance between any two vertices in $P$ is at least $4$, then any $(k+1)$-colouring of $P$ extends to a $(k+1)$-colouring of $G$.
Following Albertson, many papers on colouring extension have emerged in recent years. The following questions highlight some of the main directions of this research:
1. What if the precoloured set is a collection of connected subgraphs, as opposed to isolated vertices?
2. What about more general types of colourings? Circular colourings? Homomorphisms?
A result for extending colourings of cliques was proven in the original paper of Albertson.
Theorem (Albertson 1998): A $(k+1)$-colouring of a collection of $r$-cliques in a $k$-colourable graph $G$ extends to a $(k+1)$-colouring of $G$ provided that the distance between any two precoloured cliques is at least $6r-2$.
The distance condition was improved to $4r$ by Kostochka (see Albertson and Moore). This was shown to be nearly best possible by Albertson and Moore in 1999.
An extension theorem for circular colourings was given by Albertson and West.
Theorem (Albertson and West 2006): Let $k'/q'>k/q\geq2$. There is a distance $d^*$ so that any $(k',q')$-colouring of a collection of vertices in a $(k,q)$-colourable graph $G$ extends to a $(k',q')$-colouring of $G$ provided that the distance between any two precoloured vertices is at least $d^*$.
Albertson and West conjectured that the result of Albertson on extending precolourings of cliques would also generalize to the circular setting. Given $k/q\geq2$, the circular $(k,q)$-clique $G_{k,q}$ is defined at a graph on $\{0,1,\dots, k-1\}$ where $i\sim j$ if $q\leq |i-j|\leq k-q$. We remark that a graph $G$ is $(k,q)$-colourable if and only if there is a homomorphism $G\to G_{k,q}$.
Conjecture (Albertson and West 2006): Let $k'/q'\geq k/q +1\geq3$. There is a distance $d^*$ so that any $(k',q')$-colouring of a collection of circular $(k,q)$-cliques in a $(k,q)$-colourable graph $G$ extends to a $(k',q')$-colouring of $G$ provided that the distance between any two precoloured vertices is at least $d^*$.
In a 2012 paper, Richard Brewster and I gave an infinite family of counterexamples to this conjecture.
Theorem (Brewster and Noel 2012): Let $d^*$ be a positive integer. For any $\ell\geq0$ there exists $k'/q'\geq k/q +\ell\geq2+\ell$ so that the following is true. There is a $(k',q')$-colouring of exactly two $(k,q)$-cliques in a $(k,q)$-colourable graph $G$ so that the distance between the precoloured vertices is at least $d^*$ and the precolouring does not extend.
These counterexamples are based on constructions of so-called frozen colourings. A colouring of a graph $G$ is frozen if no vertex of $G$ can be recoloured. Frozen colourings are very important in the study of mixing colourings and graph homotopy.
As an example, the colouring of $G_{12,5}$ obtained by reducing the label of each vertex modulo $4$ is a frozen $4$-colouring.
Research Topics: Ohba's Conjecture Circular Colouring the Real Orthogonality Graph Graph Homotopy Extending Colourings Mixing Circular Colourings