Shifting Colors Along a Vizing Fan

What a Shift Does

In a partial edge coloring, one edge is left uncolored while the other edges are colored so that edges sharing a vertex receive different colors. A Vizing fan records several edges incident to one center vertex, together with information about which colors are missing at their other endpoints. Shifting moves the uncolored edge from one spoke of the fan to another. The key point is that a shift is safe only when each color is placed at a vertex where it was missing.

All graphs below are finite and simple. Fix a finite set $C$ of colors. A partial proper edge coloring is an assignment of colors from $C$ to some edges such that any two colored edges sharing a vertex have different colors. A color is missing at a vertex if no colored edge incident with that vertex has that color. Write $M(v)$ for the set of colors missing at $v$. An uncolored edge has no assigned color and does not count as an incident edge of any color.

Definition: Let $x$ be a vertex and $v_1,\dots,v_r$ distinct neighbors of $x$, where $r\ge 1$. The sequence is a fan at $x$ for a partial proper edge coloring if $xv_1$ is uncolored and, for each $i\ge 2$, the edge $xv_i$ is colored with a color missing at some earlier vertex $v_j$, where $j<i$. A selected sequence $v_1,\dots,v_k$ from the fan, in that order, is shift-compatible if for each $i=2,\dots,k$, the color on $xv_i$ is missing at $v_{i-1}$.

The fan condition permits the color on $xv_i$ to be missing at any earlier fan vertex. Shift-compatibility asks for the stronger, immediate predecessor condition along the sequence being shifted. This distinction matters: the fan condition alone does not guarantee that shifting through the vertices in order is safe.

Definition: For a shift-compatible sequence $v_1,\dots,v_k$, shifting along the sequence means, for $i=2,\dots,k$, moving the color on $xv_i$ to $xv_{i-1}$, and leaving $xv_k$ uncolored. Thus the uncolored spoke moves from $xv_1$ to $xv_k$. If $k=1$, there are no moves.

Why a Shift Preserves Properness

Proposition: Shifting along a shift-compatible sequence preserves a partial proper edge coloring. The set of colors on colored edges incident with $x$ is unchanged, and the only uncolored spoke among the selected edges becomes $xv_k$.

Proof. Assume first that $k\ge 2$. Write $c_i$ for the color on $xv_i$ before the shift, for $i=2,\dots,k$. The edges $xv_2,\dots,xv_k$ share $x$, so properness implies that $c_2,\dots,c_k$ are pairwise distinct. After shifting, each of these colors still appears on exactly one selected spoke: $c_i$ is on $xv_{i-1}$. Therefore no two colored selected spokes conflict at $x$, and the set of colors at $x$ is unchanged. At $v_{i-1}$, the new incident color is $c_i$, which is missing there by shift-compatibility. Adding it cannot create a conflict with any other colored edge at $v_{i-1}$. No other edge changes color, and $xv_k$ is left uncolored. Thus the coloring remains proper. If $k=1$, nothing changes, so the assertion also holds. $\square$

The proof identifies exactly where the hypothesis is used: each moved color must be missing at the endpoint that receives it. Properness at the center follows for a different reason: the colors are merely transferred between spokes, and the colors on those spokes were distinct already.

How Missing-Color Sets Change

Proposition: Let $v_1,\dots,v_k$ be shift-compatible, with $k\ge2$, and let $c_i$ be the original color on $xv_i$ for $2\le i\le k$. If $M'(v)$ denotes the missing-color set after the shift, then $$ M'(v_1)=M(v_1)\setminus\{c_2\},\qquad M'(v_i)=\bigl(M(v_i)\setminus\{c_{i+1}\}\bigr)\cup\{c_i\}\quad(2\le i<k), $$ and $$ M'(v_k)=M(v_k)\cup\{c_k\}. $$ The missing-color set at $x$ is unchanged.

Proof. At $v_1$, the edge $xv_1$ was uncolored, and $c_2$ was missing by shift-compatibility. After the shift, $xv_1$ receives $c_2$, so precisely that missing color is removed. At an internal vertex $v_i$, where $2\le i<k$, the old edge $xv_i$ of color $c_i$ is uncolored and $xv_{i+1}$ moves its color $c_{i+1}$ onto $xv_i$. Removing the old edge makes $c_i$ missing; adding the new color removes $c_{i+1}$ from the missing set. These colors are distinct because the original spokes meet at $x$. At $v_k$, the edge of color $c_k$ is uncolored and no selected edge replaces it, so $c_k$ becomes missing. Finally, the set of colors present at $x$ is unchanged by the preceding proposition, so its missing-color set is unchanged as well. $\square$

These formulas concern the selected vertices; other incident edges at those vertices remain as they were. In particular, the last vertex gains a missing color, while each internal vertex exchanges one missing color for another. At the first vertex, a color that was missing is used. If $k=1$, no shift occurs and every missing-color set stays unchanged.

Worked Shifts

Worked Example: Shifting Across Three Spokes

Let $G=(V,E)$ have $V=\{x,a,b,c,d\}$ and $E=\{xa,xb,xc,bd\}$. Use the palette $C=\{1,2,3,4\}$. The partial coloring is $xb=1$, $xc=2$, $bd=3$, with $xa$ uncolored. This is proper: at $x$ the two colored spokes have colors $1,2$, and at $b$ the incident colored edges have colors $1,3$.

The sequence $a,b,c$ is shift-compatible. The color on $xb$ is $1$, missing at $a$; the color on $xc$ is $2$, missing at $b$, whose colored incident edges have colors $1,3$. Shift by putting $1$ on $xa$ and $2$ on $xb$, leaving $xc$ uncolored. The edge $bd$ retains color $3$.

Before the shift, $M(a)=\{1,2,3,4\}$, $M(b)=\{2,4\}$, and $M(c)=\{1,3,4\}$. Afterward, $xa=1$, so $M'(a)=\{2,3,4\}$. At $b$, the incident colors are now $2,3$, so $M'(b)=\{1,4\}$. At $c$, the only colored incident edge before the shift had color $2$. After shifting, $xc$ is uncolored, so $c$ has no colored incident edges and $M'(c)=\{1,2,3,4\}$.

Check: At $x$, the colors on the selected spokes were $1,2$ before the shift and are still $1,2$ afterward, so the missing colors there are $\{3,4\}$ both times. At $b$, its two colored edges have distinct colors $2$ and $3$; at $a$, its only colored edge has color $1$; and at $c$, there is no colored edge. The shifted coloring is proper.

Worked Example: Tracking an Internal Vertex

Let $G=(V,E)$ have $V=\{x,a,b,c,d,p,q\}$ and $E=\{xa,xb,xc,xd,bp,cq\}$. Use $C=\{1,2,3,4\}$, and color $xb=1$, $xc=2$, $xd=3$, $bp=4$, and $cq=1$; leave $xa$ uncolored. This is proper: the colors at $x$ are $1,2,3$, those at $b$ are $1,4$, and those at $c$ are $2,1$.

The sequence $a,b,c,d$ is shift-compatible. The successive spoke colors are $1,2,3$: $1$ is missing at $a$; $2$ is missing at $b$, whose incident colors are $1,4$; and $3$ is missing at $c$, whose incident colors are $1,2$. Shift to obtain $xa=1$, $xb=2$, $xc=3$, with $xd$ uncolored. The edges $bp=4$ and $cq=1$ do not change.

At $b$, the original missing set is $\{2,3\}$, since its incident colors are $1,4$. The shift removes color $1$ from $xb$ and places color $2$ there; afterward its incident colors are $2,4$, so $M'(b)=\{1,3\}$. At $c$, the original missing set is $\{3,4\}$, since its incident colors are $1,2$. The shift replaces color $2$ on $xc$ by color $3$; afterward its incident colors are $1,3$, so $M'(c)=\{2,4\}$. At $d$, the only colored incident edge $xd$ has been uncolored; since $d$ has no other incident edges, $M'(d)=\{1,2,3,4\}$. At $a$, $xa$ receives color $1$, giving $M'(a)=\{2,3,4\}$.

Check: The colors on the selected spokes at $x$ are $1,2,3$ both before and after, so $M(x)=M'(x)=\{4\}$. At $b$, the colors $2,4$ differ; at $c$, the colors $3,1$ differ. Thus the changed coloring is proper at every vertex incident with a changed edge.

Worked Example: A Fan Sequence That Cannot Be Shifted Directly

Let $G=(V,E)$ have $V=\{x,a,b,c,q\}$ and $E=\{xa,xb,xc,bq\}$. Use $C=\{1,2,3\}$, color $xb=1$, $xc=2$, and $bq=2$, and leave $xa$ uncolored. This is proper: at $x$ the colors are $1,2$, while at $b$ they are $1,2$.

The sequence $a,b,c$ satisfies the fan condition: the color $1$ on $xb$ is missing at $a$, and the color $2$ on $xc$ is also missing at the earlier vertex $a$. But $2$ is not missing at $b$, because $bq$ already has color $2$. A direct shift in the listed order would put color $2$ on $xb$, giving two incident edges of color $2$ at $b$. That would not be proper.

The selected sequence $a,c$ is shift-compatible: color $2$ on $xc$ is missing at $a$. Shifting along it gives $xa=2$, leaves $xb=1$ and $bq=2$ unchanged, and leaves $xc$ uncolored. The colors at $x$ are still $1,2$, and those at $b$ are still $1,2$; the resulting coloring is proper.

Check: The failed direct move would make the two edges $xb$ and $bq$ both color $2$. The valid shift changes only $xa$ and $xc$, so it introduces no such conflict. The example shows why the immediate missing-color condition must be checked at each receiving vertex.

Using the Missing-Color Bookkeeping

A shift is useful because it relocates the uncolored edge while preserving properness and controlling which colors are missing at the fan vertices. The endpoint $v_k$ gains the color $c_k$, which was previously on its spoke. The center $x$ keeps exactly the same set of missing colors. Thus, if a color missing at $x$ is also missing at the new endpoint, the uncolored edge can be colored with that color. Establishing when such a color exists requires additional arguments; the shift propositions alone do not guarantee it.

Common pitfall: Do not say that the last fan vertex keeps its old colored spoke after the shift. That spoke is the one left uncolored. For instance, in the first example, $c$ had color $2$ on $xc$ before the shift and no colored incident edges afterward. Its missing set is therefore the entire palette, not a set computed by replacing color $2$ with a different color.

For reliable bookkeeping, record the status of each selected spoke, then inspect each endpoint separately: the first vertex receives a color, each internal vertex loses one color and receives another, and the last vertex loses its colored spoke. The center is checked separately by comparing the set of spoke colors before and after. These checks apply even when fan vertices have additional incident edges, because those edges are not changed by the shift.

Check Your Understanding

Use a specified palette and check properness at every affected vertex when answering.

For a shift-compatible sequence of length $k\ge2$, explain why the missing-color set at the center does not change.
At an internal fan vertex $v_i$, identify the color that becomes missing and the color that ceases to be missing.
In the first worked example, recompute $M'(b)$ directly from the colors on the edges incident with $b$.
Why does the fan condition alone not justify shifting a color onto the immediately preceding vertex?
What changes when the selected sequence has length $1$?