Combining Fans With Two-Color Chains

Why Combine a Fan with a Two-Color Chain?

In a partial edge coloring, an uncolored edge can be colored immediately if one color is missing at both endpoints. A Vizing fan organizes several edges at a common root so that shifting their colors can move the uncolored edge to a different fan vertex. A two-color chain offers another operation: switching two colors along an alternating path can change which colors are missing at its endpoints. The useful step is to coordinate these operations, keeping the coloring proper while arranging a common missing color.

All graphs in this tutorial are finite and simple. A partial proper edge coloring assigns colors to some edges so that edges sharing an endpoint receive different colors. The palette is a specified set of colors, and an edge left uncolored has no color assigned to it. For a vertex \(v\), let \(M(v)\) be the set of palette colors not used on any colored edge incident with \(v\).

Definition: A fan rooted at \(x\) is an ordered list of distinct neighbors \(y_1,\dots,y_k\) such that every edge \(xy_i\) is colored and, for each \(i>1\), the color of \(xy_i\) is missing at some earlier vertex \(y_j\), where \(j<i\). The edges \(xy_i\) are the fan edges. A shift along the fan moves the color of a later fan edge onto an earlier fan edge when that color is missing at the earlier edge's other endpoint, leaving the later edge uncolored.

The condition on the fan means that its edges are linked by missing colors. For example, if \(xy_2\) has color \(c\) and \(c\in M(y_1)\), then one may uncolor \(xy_2\) and color \(xy_1\) with \(c\). At \(x\), this is safe because the color is removed from \(xy_2\) before it is assigned to \(xy_1\). At \(y_1\), it is safe because \(c\) was missing there.

Definition: Given two distinct colors \(\alpha,\beta\), the \((\alpha,\beta)\)-subgraph consists of the colored edges of those two colors and their incident vertices. Its connected components are paths, cycles, or isolated vertices, because at most one edge of each color meets a vertex. A component that is a path is called an \((\alpha,\beta)\)-chain. Switching a chain means interchanging \(\alpha\) and \(\beta\) on every edge of that chain.

A switch preserves properness: at each vertex on the chain, the incident chain edges still have distinct colors, and no edge of either color outside the chain meets that vertex. If a color is missing at an endpoint before the switch, the other color becomes missing there afterward. This endpoint effect is the connection to a fan.

When the Chain Avoids the Fan Vertex

Proposition: Suppose \(\alpha\in M(x)\), \(\beta\in M(y)\), and \(P\) is the \((\alpha,\beta)\)-component containing \(x\). If \(y\) is not on \(P\), switching the colors on \(P\) makes \(\beta\) missing at both \(x\) and \(y\).

Proof. Because \(\alpha\) is missing at \(x\), at most one edge of the \((\alpha,\beta)\)-subgraph is incident with \(x\): there can be no \(\alpha\)-edge there and at most one \(\beta\)-edge. Thus \(x\) is an endpoint of the component \(P\), or \(P\) is the isolated vertex \(x\). After switching, \(\beta\) is missing at \(x\). The switch changes only edges in \(P\), and \(y\notin P\), so the edges incident with \(y\) are unchanged. In particular, \(\beta\) remains missing at \(y\). Therefore \(\beta\) is missing at both vertices. \(\square\)

The fan helps identify useful choices of \(y\) and colors: its defining property records which colors are missing at earlier fan vertices. The proposition itself has a simple test. Follow the alternating chain from the root; if the target fan vertex is outside that component, switching supplies a common missing color without changing the target's incident edges.

Worked Example: The Chain Stops Before the Fan Vertex

Let \(V=\{x,a,b\}\), \(E=\{xa,xb\}\), with palette \(\{1,2,3\}\). The partial coloring is \(c(xa)=3\) and \(c(xb)=2\). Consider the fan rooted at \(x\) with order \(y_1=a,y_2=b\): the color \(2\) on \(xb\) is missing at \(a\). Here \(1\in M(x)\), and \(3\in M(b)\).

Follow the \((1,3)\)-component containing \(x\). The edge \(xa\) has color \(3\). Vertex \(a\) has no incident edge of color \(1\), so the chain stops there; \(b\) is outside this component. Switch on the chain: \(xa\) changes from color \(3\) to color \(1\), and \(xb\) remains color \(2\). Now \(3\) is missing at \(x\), and it is still missing at \(b\).

Check: at \(x\), the only colored incident edges now have colors \(1\) and \(2\), so \(M(x)=\{3\}\). At \(b\), the only incident edge has color \(2\), so \(M(b)=\{1,3\}\). Thus \(3\in M(x)\cap M(b)\), as claimed, and the coloring remains proper.

When the Chain Reaches the Fan

If the chain does reach the chosen fan vertex, switching alone may not create a common missing color there. The fan can still be useful: after the switch, a color may be missing at an earlier fan vertex and can be shifted onto its fan edge. The following two-edge configuration gives a precise instance of this combination.

Theorem: Let \(x,y_1,y_2\) form a fan with colored edges \(e_1=xy_1\) and \(e_2=xy_2\). Suppose their colors are \(c(e_1)=\gamma\) and \(c(e_2)=\beta\), with \(\beta\in M(y_1)\) and \(\gamma\in M(y_2)\). Suppose also that \(\alpha\in M(x)\), where \(\alpha,\beta,\gamma\) are distinct, and that the \((\alpha,\beta)\)-chain from \(x\) is a path ending at \(y_1\) whose first edge is \(e_2\). Then a chain switch followed by a fan shift leaves \(e_2\) uncolored and makes \(\gamma\) missing at both \(x\) and \(y_2\).

Proof. Switch \(\alpha\) and \(\beta\) on the chain from \(x\) to \(y_1\). Since \(\alpha\) was missing at \(x\), the switch makes \(\beta\) missing at \(x\). Since \(\beta\) was missing at \(y_1\) and the chain ends there, the last edge of the path has color \(\alpha\); after the switch, \(\alpha\) is missing at \(y_1\). In particular, \(e_2\), which was colored \(\beta\), is now colored \(\alpha\). The edge \(e_1\) still has color \(\gamma\), because \(\gamma\) is distinct from both chain colors.

Now uncolor \(e_2\), then assign color \(\alpha\) to \(e_1\). This shift is proper: \(\alpha\) is missing at \(y_1\), and uncoloring \(e_2\) first ensures that \(\alpha\) is free at \(x\). The color \(\beta\) remains missing at \(x\), and \(\gamma\) is now missing there because \(e_1\) no longer has color \(\gamma\). At \(y_2\), \(\gamma\) was missing initially; the chain switch uses only \(\alpha,\beta\), and uncoloring \(e_2\) cannot introduce a \(\gamma\)-edge. Hence \(\gamma\) remains missing at \(y_2\). Thus \(\gamma\) is missing at both \(x\) and \(y_2\), with \(e_2\) uncolored. \(\square\)

The order of operations matters. The switch creates the missing color \(\alpha\) at \(y_1\); the fan shift uses that vacancy. The resulting common missing color is \(\gamma\), not necessarily either of the colors used on the chain.

Worked Example: Switching the Chain, Then Shifting the Fan

Let \(V=\{x,a,b,z,w\}\), \(E=\{xa,xb,bz,zw,wa\}\), with palette \(\{1,2,3\}\). Color the edges by \(c(xa)=3\), \(c(xb)=2\), \(c(bz)=1\), \(c(zw)=2\), and \(c(wa)=1\). This is proper: the colors at \(x,a,b,z,w\) are respectively \(\{3,2\},\{3,1\},\{2,1\},\{1,2\},\{2,1\}\). The ordered fan \((x,a,b)\) satisfies its condition because color \(2\) on \(xb\) is missing at \(a\).

Set \(\alpha=1\), \(\beta=2\), and \(\gamma=3\). The chain from \(x\) is \(x,b,z,w,a\), with edge colors \(2,1,2,1\). It ends at \(a\), where color \(2\) is missing. Initially \(1\in M(x)\) and \(3\in M(b)\).

Switch along the whole chain. The edge colors become \(c(xb)=1\), \(c(bz)=2\), \(c(zw)=1\), and \(c(wa)=2\); \(c(xa)=3\) is unchanged. Now \(1\) is missing at \(a\), so shift the fan: uncolor \(xb\), then change \(xa\) from color \(3\) to color \(1\). The final colored edges are \(xa=1\), \(bz=2\), \(zw=1\), and \(wa=2\), while \(xb\) is uncolored.

Check: at \(x\), color \(1\) is used on \(xa\), so \(M(x)=\{2,3\}\). At \(b\), the remaining colored incident edge \(bz\) has color \(2\), so \(M(b)=\{1,3\}\). Therefore \(3\) is missing at both \(x\) and \(b\). Each vertex's colored incident edges have distinct colors, confirming that the final partial coloring is proper.

A Second Chain Check

Worked Example: An Avoiding Chain in a Larger Fan

Let \(V=\{x,p,q,r\}\), \(E=\{xp,xq,pr\}\), with palette \(\{1,2,3\}\) and coloring \(c(xp)=3\), \(c(xq)=2\), \(c(pr)=1\). The fan \((x,p,q)\) is valid because color \(2\) on \(xq\) is missing at \(p\). The root misses color \(1\), and \(q\) misses color \(3\).

The \((1,3)\)-chain from \(x\) is \(x,p,r\): its edge colors are \(3,1\), and it stops at \(r\), which has no incident edge of color \(3\). It does not contain \(q\). Switching changes \(xp\) to color \(1\) and \(pr\) to color \(3\); the edge \(xq\) remains color \(2\).

Check: after the switch, \(x\) has incident colors \(1,2\), so color \(3\) is missing there. Vertex \(q\) still has only its color-\(2\) edge \(xq\), so color \(3\) is also missing at \(q\). Thus the chain-avoidance proposition applies even though the fan has another vertex.

Common Pitfall: Switching Only Part of a Chain

A chain switch interchanges the two colors on the entire chain component, not just on the edge incident with the root. In the preceding two-edge fan example, changing only \(xb\) from color \(2\) to color \(1\) would leave \(bz\) with color \(1\). The two edges \(xb\) and \(bz\) meet at \(b\), so the coloring would no longer be proper. The correct switch changes every chain edge: \(xb:2\to1\), \(bz:1\to2\), \(zw:2\to1\), and \(wa:1\to2\). Alternation is what preserves distinct colors at internal chain vertices.

Also distinguish the two outcomes. If the chain avoids the selected fan vertex, the switch directly gives a common missing color. If it reaches that vertex, a further fan shift may be needed; the proved two-edge configuration specifies hypotheses under which that combination works. In either case, check missing colors after each operation rather than inferring them from the original coloring.

Check Your Understanding

For each question, track the palette colors at every affected vertex.

If \(\alpha\) is missing at the root and a fan vertex \(y\) is outside the \((\alpha,\beta)\)-component containing the root, what is missing at both vertices after the switch?
In a two-edge fan, why must the color of the later edge be missing at the earlier fan vertex before shifting?
In the chain-and-fan theorem, which color becomes missing at \(y_1\) after the chain switch, and why?
Explain why the common missing color in that theorem is \(\gamma\), even though the chain uses \(\alpha\) and \(\beta\).
In the worked chain-switch example, what conflict occurs if only edge \(xb\) is recolored and the rest of the chain is left unchanged?