Missing Colors in Partial Edge Colorings

Colors Available at a Vertex

In a partial edge coloring, some edges have already been assigned colors and others remain uncolored. To decide whether one of those uncolored edges can be colored without changing the existing assignments, we need to know which colors are still available at each endpoint. The missing-color set records exactly that information. It is local to a vertex: a color can be missing at one endpoint even if it is used elsewhere in the graph.

Throughout, graphs are finite and simple. Fix a finite palette \(\mathcal C\) of \(k\) colors. A partial proper edge coloring of \(G=(V,E)\) consists of a subset \(E_\phi\subseteq E\) of colored edges and an assignment \(\phi:E_\phi\to\mathcal C\) such that any two colored edges sharing an endpoint have different colors. Edges in \(E\setminus E_\phi\) are uncolored. Write \(d_\phi(v)\) for the number of colored edges incident with \(v\).

Only colored edges are considered when forming \(M_\phi(v)\). An uncolored edge incident with \(v\) does not use a color and therefore does not remove any color from the set. Also, “missing” does not mean unused throughout the graph: a color used far from \(v\) can still be missing at \(v\).

Counting Missing Colors

Proof. At \(v\), the \(d_\phi(v)\) colored incident edges have pairwise distinct colors, by properness. Exactly \(d_\phi(v)\) of the \(k\) palette colors are therefore present at \(v\), leaving \(k-d_\phi(v)\) missing. Sum this equality over all vertices. Each vertex contributes \(k\) to the first term, giving \(kn\). Each colored edge has two distinct endpoints, so it contributes \(1\) to \(d_\phi(v)\) at each endpoint and is counted twice in \(\sum_{v\in V}d_\phi(v)\). Consequently that sum is \(2m_\phi\), and \(\sum_{v\in V}|M_\phi(v)|=kn-2m_\phi\). If \(V\) is empty, both sums over vertices are empty and \(n=m_\phi=0\), so the same equality holds. \(\square\)

This gives both a local and a global check. Locally, the number missing depends on how many colored edges meet the vertex, not on how many uncolored edges meet it. Globally, the sum of all missing-set sizes counts available colors at vertex-ends; a color missing at two vertices contributes twice.

The Immediate-Color Test

Proof. Suppose first that \(c\in M_\phi(u)\cap M_\phi(v)\). By the definition of missing sets, no colored edge incident with \(u\) has color \(c\), and no colored edge incident with \(v\) has color \(c\). Assign color \(c\) to \(uv\). The new edge then conflicts with no previously colored edge at either endpoint, and all other pairs of colored edges remain unchanged. The coloring is still proper.

Conversely, suppose \(uv\) can be colored with some \(c\in\mathcal C\) while leaving all existing assignments unchanged. If a colored edge incident with \(u\) already had color \(c\), the two edges would share \(u\) and have the same color, contradicting properness of the extended coloring. So \(c\in M_\phi(u)\). The same argument at \(v\) gives \(c\in M_\phi(v)\). Hence \(c\in M_\phi(u)\cap M_\phi(v)\), so that intersection is nonempty. Both directions use the same fixed palette; allowing a new color would be a different question. \(\square\)

The test concerns an immediate extension: one assigns a color to the chosen edge and leaves all previous assignments alone. If the intersection is empty, the theorem says no such direct assignment is possible with the current palette. It does not say that the edge can never be colored after other edges are recolored or the palette is enlarged.

A Useful Consequence and a Common Mistake

Proof. For every vertex \(v\), the number \(d_\phi(v)\) of colored incident edges is at most its degree \(\deg(v)\), which is at most \(\Delta(G)\). The counting proposition gives \(|M_\phi(v)|=k-d_\phi(v)\ge k-\Delta(G)\ge1\). Thus each missing set is nonempty. This does not imply that the missing sets at the two endpoints of a particular uncolored edge intersect; the triangle example demonstrates that distinction. \(\square\)

This simple consequence explains why missing-color sets are useful in arguments using a palette of \(\Delta(G)+1\) colors: there is always at least one locally available color at each vertex. But an edge requires one color available at both endpoints, which is a stronger condition.

Common mistake: treating an uncolored edge as if its color were missing at both endpoints. In the triangle example, one might incorrectly say that \(R\) is missing at \(b\) because \(bc\) is uncolored. That is wrong: \(ab\) is colored \(R\) and is incident with \(b\). The definition excludes colors used by any colored incident edge, regardless of which other edges are uncolored. The correct sets are \(M_\phi(b)=\{B\}\) and \(M_\phi(c)=\{R\}\), so there is no shared color.

When testing an uncolored edge, compute the missing set separately at each endpoint and then take the intersection. A color that is missing at one endpoint alone does not suffice. If the intersection is empty, report only that immediate coloring with the fixed palette is impossible; a later recoloring argument may change the missing sets.