A note on connected greedy edge colouring

To see the first claim, suppose that we assign $xx^{\prime}$ and $yy^{\prime}$ different colours. One of the colour classes must then cover an odd number of vertices from $Q_{\Delta}$ (because it covers an even number of vertices in $Q_{\Delta}^{+}$ as any colour class of an edge colouring of $Q_{\Delta}^{+}$ forms a matching). Let $v\in V(Q_{\Delta})$ be a vertex not covered by this colour class. Since $v$ has degree $\Delta$, there are edges of $\Delta$ different colours incident to it. Hence we have used at least $\Delta+1$ colours.

To see the second claim, fix any $\Delta$-edge colouring $\alpha$ of $Q_{\Delta}^{+}$ with $\alpha(xx^{\prime})=i$. Let $z\in\{x,x^{\prime}\}$ be the vertex of degree $\Delta$. We can now always create an ordering of the edges leading to the edge colouring $\alpha$. Indeed, we first colour the edge incident to $z$ which needs to get colour $1$, then the edge incident to $z$ that needs to get colour $2$, etc, until we coloured all edges incident to $z$. We then pick a neighbour of $z$ of degree $\Delta$ and colour all edges incident to this one in a similar order. We continue like this until all edges have been coloured. ∎

We extend $\Delta-2$ copies of $Q_{\Delta}^{+}$ to the graph $H$. We first glue all these copies on their respective vertices labelled $x^{\prime}$ and $y^{\prime}$. We then obtain the graph $H$ by adding a new vertex $u$ adjacent to the (merged) vertices $x^{\prime}$ and $y^{\prime}$ and a new vertex $s$ adjacent to $u$ (see Figure 2).

Let $\alpha$ be a $\Delta$-edge colouring. Since $\alpha(x^{\prime}u)\neq\alpha(y^{\prime}u)$, we find that there exists a $Q_{\Delta}^{+}$ copy for which $\alpha(xx^{\prime})=\alpha(yy^{\prime})=\alpha(su)$, where $x$ and $y$ are the vertices in this copy adjacent to $x^{\prime}$ and $y^{\prime}$ respectively. If we start the colouring from an edge incident to $u$, then one of the edges in $\{xx^{\prime},yy^{\prime}\}$ is the first edge to be coloured from $Q_{\Delta}^{+}$; since $x^{\prime}$ has degree $\Delta-1$, this edge will not get colour $\Delta$. Combined with Lemma 4, this shows that no connected $\Delta$-edge colouring starting from $su$ can exist in which the edge $su$ is precoloured $\Delta$.

On the other hand, if $su$ gets a colour strictly smaller than $\Delta$, then we first may colour $x^{\prime}u$, then all edges incident to $x^{\prime}$, and finally by Lemma 4 we can further extend the connected ordering in such a way that all copies of $Q_{\Delta}^{+}$ are $\Delta$-edge coloured while no edge incident with $y^{\prime}$ receives colour $\Delta$. So we have at least one colour leftover for $y^{\prime}u$ (which will in fact need to get colour $\Delta$). ∎

Let $d=\Delta-1$, and let $G$ be an $n$-vertex $d$-regular graph. We transform $G$ into a graph $G^{\prime}$ of maximum degree $\Delta$ such that $\chi^{\prime}(G)=d$ if and only if $\chi^{\prime}_{c}(G^{\prime})=\chi^{\prime}(G^{\prime})$. In fact, $\chi^{\prime}(G^{\prime})=\Delta$ and $|V(G^{\prime})|\leq\Delta^{2}2^{\Delta}n$. This reduction proves the theorem since deciding whether $\chi^{\prime}(G)=d$ is NP-hard on $d$-regular graphs for all $d\geq 3$, as shown by Leven and Galil [4].

Let $\Delta=d+1$ and let $H$ be the graph from Lemma 5. For each $v\in V(G)$, we create a graph $G_{v}$ by merging $\Delta-1$ copies of $H$ on their special vertex $s$ (see Figure 3). The graph $G^{\prime}$ is obtained from $G$ by connecting $G_{v}$ to $v$ via an edge for each $v\in V(G)$; for $v,v^{\prime}$ distinct vertices of $G$, the graphs $G_{v}$ and $G_{v^{\prime}}$ are disjoint and have no edges between them. Note that $\chi^{\prime}(G^{\prime})=\Delta$.

Suppose first that our $d$-regular graph $G$ can be coloured using $d$ colours. Fix a $d$-edge colouring $\alpha$ of $G$. There is a connected ordering of the edges of $G$ that results in the edge colouring $\alpha$. Indeed, since $G$ is $d$-regular, whenever we have ‘reached’ a vertex we can assign the edges incident to this vertex the desired colours, starting from the edge coloured $1$, continuing with the edge coloured $2$ etc. We may then colour the edge from $v$ to $G_{v}$ with colour $d+1$ for all $v\in V(G)$. Continuing in the various copies of $H$, the corresponding edge $su$ gets a colour $<d+1=\Delta$ and hence by Lemma 5 there is a connected ordering in which we can edge colour these with $\Delta$ colours. So $\chi_{c}^{\prime}(G^{\prime})=\chi^{\prime}(G^{\prime})$.

Suppose now that $G$ is not $d$-edge colourable. For contradiction, suppose there is a $\Delta$-edge colouring $\alpha$ that can be obtained via a connected ordering. Since $G$ is not $d$-edge colourable, $\alpha(vv^{\prime})=d+1$ for some $vv^{\prime}\in E(G)$. The two edges between $v,v^{\prime}$ and $G_{v},G_{v^{\prime}}$ are then not coloured $\Delta$. As $G_{v}$ and $G_{v^{\prime}}$ are not connected to each other, we may assume that these edge are coloured before any of the edges in $G_{v}$ are coloured. Since $s$ has degree $\Delta$, there is then a copy of $H$ with vertex $u$ connecting to $s$ in $G_{v}$ for which $su$ has colour $\Delta$ and this is the first edge of $H$ that is coloured; this contradicts Lemma 5. So $\chi^{\prime}_{c}(G^{\prime})>\chi^{\prime}(G^{\prime})$. ∎

We prove the lemma by induction on $k$. If $G$ is a connected graph with $\chi^{\prime}(G)=1$, then $G$ is a single edge. Hence the lemma is true for $k=1$. Suppose now that we have proven the lemma for all $k^{\prime}<k$ for some integer $k\geq 2$.

Let $\alpha:E(G)\to[k]$ be a $k$-edge colouring of $G$ and let $u,v\in V(G)$. For $u,v$ distinct, we say $u$ strongly reaches $v$ in the colouring $\alpha$ if $uv\in E(G)$ and either $\alpha(uv)<k$ or the degree of $u$ is $k$. Each vertex strongly reaches itself. We now define reachability as the transitive closure of strong reachability: we say $u$ reaches $v$ in the colouring $\alpha$ if there is a sequence $u=v_{0},v_{1}\dots,v_{\ell}=v$ of vertices in $G$ such that $v_{i-1}$ strongly reaches $v_{i}$ for all $i\in[\ell]$.

We first show that for every vertex $v$, there exists a $k$-edge colouring of $G$ such that $v$ reaches all vertices of $G$ in this colouring. Take a $k$-edge colouring $\alpha$ of $G$ which maximises the number of vertices that $v$ can reach. Suppose that $v$ cannot yet reach all vertices. We will strictly increase the set of vertices that $v$ can reach through a series of Kempe changes.

Let $A\subseteq V(G)$ be the set of vertices that $v$ can reach in $\alpha$ and let $B=V(G)\setminus A$. Note that as $v$ reaches itself, $v\in A$. Since $G$ is connected, there must be an edge $su$ from some $s\in A$ to some $u\in B$. By the definition of strong reachability, we find that $s$ has degree strictly smaller than $k$ and that $\alpha(su)=k$. Hence $s$ misses a colour $x\in[k-1]$, that is, it has no edge incident of colour $x$.

Suppose first that $u$ has degree $<k$. If vertex $u$ misses colour $x$ as well, then the edge $su$ forms a $(k,x)$-component on its own and a $(k,x)$-Kempe change switches the colour of $su$ to $x$. This adds the vertex $u$ to the set of vertices that $v$ can reach, increasing the set of vertices $v$ can reach as desired. Hence we may assume that $u$ misses some colour $y$ but does not miss colour $x$. Then $y<k$ and there is some edge $e$ incident to $u$ coloured $x$. Since all edges between $A$ and $B$ are coloured $k$, the $(x,y)$-component of $e$ stays within $G[B]$. Hence we may perform an $(x,y)$-Kempe change on this component without affecting the set of vertices that $v$ can reach. Now we are back in the case in which $u$ and $s$ both miss colour $x$, which we already handled.

Suppose now that vertex $u$ has degree $k$. Let $e$ denote the edge coloured $x$ incident to $u$. Note that the $(x,k)$-component $C$ of $e$ is a path (of which one endvertex is $s$). If it stays within $G[B]$, then performing an $(x,k)$-Kempe change on $e$ recolours $su$ with colour $x$ without affecting the colours in $G[A]$ and hence strictly enlarges the set of vertices that $v$ can reach. So we may assume that $C$ intersects $A$ a second time, say $s^{\prime}\in A$ is the vertex closest to $s$ in the path $C$. Since $s^{\prime}$ has an edge incident with $B$, we find that it has degree $<k$. Hence it has some colour $y<k$ missing. Once we ensure $x$ is missing at $s^{\prime}$, we can do an $(x,k)$-Kempe change on the component of $e$ and strictly increase the set of vertices that $v$ can reach.

If $s^{\prime}$ has an edge incident with colour $x$, then consider the $(x,y)$-component of this edge. This has to stay within $A$ and performing a Kempe change on it will not affect the set of vertices that $v$ can reach since $x,y<k$. The only problem is that this chain $C^{\prime}$ could include the vertex $s$. Here is where we use that the graph is bipartite: as can be seen in Figure 4, this would create an odd cycle in the graph, since there is an odd number of edges in $C$ between $s$ and $s^{\prime}$ and an even number of edges in $C^{\prime}$ between $s$ and $s^{\prime}$ (since they have different colours missing). Hence we may perform the $(x,y)$-switch without affecting the missing colour of $s$, and can then perform the $(x,k)$-switch as desired.

This shows we can always strictly increase the set of vertices that $v$ can reach. This contradicts the maximality of $\alpha$. Hence there exists a colouring $\alpha$ in which $v$ can reach all vertices.

Let $C_{1},\dots,C_{\ell}$ denote the connected components of $G$ when we remove all edges of $G$ coloured $k$ in $\alpha$, where $v\in C_{1}$. We will show that there is a connected ordering starting from $v$ that leads to a $k$-edge colouring of $G$ which is a $(k-1)$-edge colouring when restricted to any $C_{i}$. Since $v$ can reach everything in $\alpha$, after possibly renumbering $C_{2},\dots,C_{\ell}$, we can find vertices

for $i=1,\dots,\ell$, such that for all $i\in[\ell-1]$, $s_{i}$ can strongly reach $v_{i+1}$ (‘reach in one step’) and hence $d_{G}(s_{i})=k$ (since we already know $\alpha(s_{i}v_{i+1})=k$ by the definition of the components).

Since $C_{1}$ is a connected bipartite graph with $\chi^{\prime}(C_{1})\leq k-1$, there exists a connected ordering starting from $v$ that $(k-1)$-edge colours $C_{1}$ by the induction hypothesis. By the definition of the components, all edges incident to $s_{1}$ except for $s_{1}v_{2}$ have now been coloured. We colour the edge $s_{1}v_{2}$ next; this obtains colour $k$. Since $C_{2}$ is a connected bipartite graph with $\chi^{\prime}(C_{2})\leq k-1$, there exists a connected ordering starting from $v_{2}$ that $(k-1)$-edge colours $C_{2}$ by the induction hypothesis. We extend our previous ordering by this connected ordering and continue like this until we have coloured all edges within the components. We then colour the edges between the components; since colour $k$ will always be available to them, they will all receive a colour at most $k$. ∎

In this proof, we will omit the $\Delta$ from $\Delta$-reach. By Vizing’s theorem [6], $G$ has at least one $(\Delta+1)$-edge colouring $\alpha$. We choose such a colouring $\alpha$ that maximises the size of the set $A$ of vertices that $v$ can reach in $\alpha$. Let $B=V(G)\setminus A$ be the set of vertices that $v$ cannot reach.

Suppose that $A\neq V(G)$. The edges between $A$ and $B$ are of colour $\Delta$ or $\Delta+1$. Let $C\subseteq B$ be the neighbours of $A$ via edges coloured $\Delta$. Let $D\subseteq B$ the set of vertices adjacent to a vertex in $C$ (which a priori might overlap with $C$). We claim that we can obtain an edge colouring in which $v$ can reach a strictly larger set of vertices than $A$ (contradicting the maximality of $A$) as soon as one of the following properties holds.

• (1)

  $C$ is empty, i.e. there is no $\Delta$-edge between $A$ and $B$.

• (2)

  There is an $(x,\Delta)$-Kempe chain with $x<\Delta$ which is a path between a vertex in $A$ and a vertex in $B$.

• (3)

  Some $c\in C$ has a colour $x\in[\Delta-1]$ missing.

• (4)

  Some $d\in D$ misses colour $\Delta$ or $\Delta+1$.

We will prove the claim after we show that we can assume one of $(1)-(4)$ holds. We suppose all properties above do not hold. Since (1) fails, we know there is an edge from some $a\in A$ to some $c\in C$ (which has colour $\Delta$ by definition of $C$). Since $c$ is not reachable, there is a colour $x<\Delta$ missing at $a$. Since (3) fails, $c$ is incident to an edge $cd$ of colour $x$. As $(4)$ fails, we know that there is some colour $y<\Delta$ missing at $d$. Consider a $(\Delta,y)$-Kempe chain starting at $d$. Since (2) fails, it stays within $B$. After performing the switch, there is a vertex in $D$ with no edge coloured $\Delta$, contradicting with (4) failing.

To prove the claim in case (1), suppose that there are no edges coloured $\Delta$ between $A$ and $B$. Since $G$ is connected, there exists an edge from some $a\in A$ to some $b\in B$. Then $\alpha(ab)=\Delta+1$. Let $x<\Delta+1$ be the smallest colour missing at $a$. Since $b$ has the edge $ab$ incident in colour $\Delta+1$, $b$ misses some colour $y<\Delta+1$. We do an $(x,y)$-Kempe change on the component of $b$ (this could be empty). Since all the edges between $A$ and $B$ are coloured $\Delta+1$, this chain stays within $B$. After the switch both $a$ and $b$ miss the colour $x$. We may recolour the edge $ab$ with colour $x$, and now the set of vertices that $v$ can reach has increased (since $v$ can now reach $b$ as well).

To prove the claim in case (2), suppose that some $(x,\Delta)$-chain for $x<\Delta$ starts in $u\in B$ and contains a vertex $s$ from $A$. Let $a\in A$ and $b\in B$ such that $ab$ is the closest edge between $A$ and $B$ in this chain to $s$. As $x<\Delta$, we find $\alpha(ab)=\Delta$. Thus $a$ must have some colour $y<\Delta$ missing (since $b$ cannot be reached). The $(x,y)$-chain starting at $a$ will stay within $A$ and switching it does not affect which vertices $v$ can reach. So we may assume that $x$ is missing at $a$ and the $(x,\Delta)$-component of $a$ is a path between $a$ and $u$ that only intersects $A$ in the vertex $a$. A Kempe change on this component strictly increases the set of vertices that $v$ can reach.

We now prove the claim assuming (3). Suppose that $c\in C$ has a colour $x<\Delta$ missing. Let $a\in A$ with $\alpha(ac)=\Delta$ (which exists by the definition of $C$). Let $y<\Delta$ be a colour missing at $a$. The $(x,y)$-chain starting at $c$ stays in $B$, and hence we may perform a switch and then recolour $ac$ to $y$ in order to increase the set of vertices that $v$ can reach.

Finally, we prove the claim from (4). Suppose $d\in D$ misses colour $\Delta$ or $\Delta+1$. Let $c\in C$ be the vertex $d$ is adjacent to. By (3) we are done unless $c$ only has the colour $\Delta+1$ missing. If $\Delta+1$ is missing at $d$, then we recolour $cd$ to colour $\Delta+1$ in order to reduce to (3). So $\Delta$ is missing at $d$. Let $a\in A$ with $\alpha(ac)=\Delta$. Let $y=\alpha(cd)<\Delta$ and let $x<\Delta$ be a missing colour at $a$. We may perform an $(x,y)$-Kempe change starting at $a$ to ensure that $a$ misses colour $y$. The only vertices on the $(y,\Delta)$-Kempe chain containing $c$ are then $a$ and $d$. After we switch this chain, the set of vertices that $v$ can reach has strictly increased again. ∎

Let $G$ be a graph of maximum degree 3. Pick a vertex $v\in V(G)$. Let $\alpha$ be a $4$-edge colouring of $G$ in which $v$ can $3$-reach all other vertices of $G$; this exists by the lemma above.

The proof follows the same argument as the second half of the proof of Theorem 2, now using the fact that any $(1,2)$-component can be $2$-edge coloured in a connected greedy fashion starting from any vertex instead of applying the induction hypothesis.

Let $C_{1}$ be the $(1,2)$-component of $v$. After doing a $(1,2)$-Kempe change if needed, we can colour $C_{1}$ in a connected greedy fashion starting from $v$. If $G$ has more components, then since $v$ can $3$-reach all other vertices, there must be a $(1,2)$-component $C_{2}\neq C_{1}$ and vertices $v_{2}\in C_{2}$ and $s_{1}\in C_{1}$ such that $s_{1}v_{2}\in E(G)$, and either $\alpha(s_{1}v_{2})<3$ or $s_{1}$ has incident edges in colours $1,\dots,\alpha(s_{1}v_{2})$ in $\alpha$. Since $s_{1}$ and $v_{2}$ are in different $(1,2)$-components, we conclude the latter holds. Since $G$ has maximum degree $3$, it follows that $\alpha(s_{1}v_{2})=3$. Hence all edges incident to $s_{1}$ have been coloured apart from $s_{1}v_{2}$, which we put next in the connected ordering. After performing a $(1,2)$-switch if needed, we $2$-edge colour the edges of $C_{2}$ in a connected greedy fashion starting from $v_{2}$. (Note that there might be no edges to colour in this step, as the component might consist of only $v_{2}$.) As long as the edges of some $(1,2)$-component have not been coloured, we can continue the connected ordering in a similar fashion. The resulting (partial) colouring has the same $(1,2)$-components as $\alpha$ and coloured an edge $3$ if and only if it has colour $3$ in $\alpha$. We finish the connected ordering by first colouring the edges coloured $3$ by $\alpha$ and then the edges coloured $4$ by $\alpha$; all these edges receive a colour at most $4$. ∎