Vizing Fans in Partial Colorings

Why Fans Organize a Partial Edge Coloring

In an edge-coloring argument, an uncolored edge \(xy\) is often the immediate obstacle: its endpoints may have no common missing color. A Vizing fan records selected neighbors of one endpoint, together with a specific reason each selected edge is relevant. The reason is a color-incidence condition: the color on each selected edge after the first is missing at an earlier leaf of the fan. The definition packages these incidences into an ordered structure; it does not itself recolor any edge.

Throughout, graphs are finite and simple. Let \(C\) be a finite set of colors. A proper partial edge coloring is a function \(\varphi\) from some subset of \(E(G)\) to \(C\), such that any two colored edges with a common endpoint have different colors. Edges outside the domain of \(\varphi\) are uncolored. For a vertex \(v\), its missing-color set is

Thus a color is missing at \(v\) precisely when no colored edge incident with \(v\) has that color. This definition refers to the current partial coloring and the chosen palette \(C\). A color may be missing at several vertices, and it may be unused on the entire graph.

The order matters. The condition for \(xy_i\) refers only to leaves earlier in the sequence, not to later ones. The earlier leaf \(y_j\) need not be the immediately preceding leaf \(y_{i-1}\). The edge color is missing at \(y_j\), not necessarily at the root \(x\). Properness also implies that the color of \(xy_i\) is not missing at \(y_i\), since that colored edge is incident with \(y_i\).

How to Test and Extend a Fan

To test a proposed sequence, first verify that the initial edge is uncolored and all listed leaves are distinct neighbors of the root. Then inspect each later leaf in order: its root edge must be colored, and that edge’s color must be missing at at least one earlier leaf. No condition requires every color in the palette to appear, or every neighbor of the root to belong to the fan.

Proof. Since the original leaves are distinct neighbors of \(x\), the first \(s\) leaves are also distinct neighbors of \(x\). Their first edge \(xy_1\) is the same uncolored edge as before. For each index \(i\) with \(2\le i\le s\), the fan condition in the original sequence supplies some \(j<i\) such that \(xy_i\) is colored and \(\varphi(xy_i)\in M_\varphi(y_j)\). Both \(i\) and \(j\) are at most \(s\), so this same condition holds in the initial segment. Thus the initial segment satisfies the definition. \(\square\)

A fan can be built one leaf at a time. Once \(xy_1\) is chosen as the uncolored starting edge, a new neighbor \(z\) can be appended exactly when \(z\) is not already listed, \(xz\) is colored, and its color is missing at one of the leaves already listed. A fan is maximal if no such one-leaf extension is possible. Maximal means that it cannot be extended under this rule; it does not mean that it has the greatest length among all fans in the graph.

Proof. Initially, the sequence \((y_1)\) is a fan: it contains one neighbor of \(x\), and there are no later leaves whose conditions need checking. At any step, append only a neighbor not already listed whose colored root edge has a color missing at an earlier listed leaf. This preserves distinctness and verifies the required condition for the newly appended leaf; conditions for leaves already listed are unchanged. The sequence therefore remains a fan after every step. Since \(x\) has exactly \(\deg(x)\) neighbors and no neighbor can be listed twice, at most \(\deg(x)\) leaves can be added. The procedure must stop after finitely many additions. It stops only when there is no unlisted neighbor eligible for addition, which is exactly the condition that no one-leaf extension is possible. Hence the final fan is maximal and has at most \(\deg(x)\) leaves. \(\square\)

Worked Examples

Reading the Incidence Condition Correctly

The condition can also be recorded as a directed dependency relation on the listed leaves: draw an arrow from \(y_j\) to \(y_i\) when the color of \(xy_i\) is missing at \(y_j\). Each leaf after the first must have at least one incoming arrow from an earlier leaf. Since every arrow goes from a smaller index to a larger index, this relation has no directed cycle.

Proof. By definition, an arrow from \(y_j\) to \(y_i\) is included only when \(j<i\). If a directed cycle existed, its arrows would give a strict chain of increasing indices that returned to its starting index. A sequence of strict increases cannot return to its initial value, so no directed cycle exists. \(\square\)

This viewpoint emphasizes that the fan is an ordered record of available color incidences, not just a collection of edges around \(x\). In the second example, the edge \(uc\) depends on the earlier leaf \(a\), even though the immediately previous leaf \(b\) does not miss color \(2\).

Common mistake: testing colors at the root. In the first example, \(r\) is incident with colors \(1,2,3\), so its missing set is \(\{4\}\). A mistaken test might reject \(b\) because the color on \(rb\) is \(1\), which is not missing at \(r\). The fan condition does not ask for the color of \(xy_i\) to be missing at \(x\). The correct test is \(1\in M_\varphi(a)\), which holds, so \(b\) can be appended. Always compare the color of a later root edge with the missing-color sets of earlier leaves.

Fans matter because they organize which colors are missing where, while keeping all the relevant edges attached to one root. Their definition is local and can be checked directly from a partial coloring. The maximality guaranteed by the greedy construction says only that no eligible neighbor can be added at the end; it makes no claim about how a fan may be changed or whether a different fan is longer.