Edge coloring ($c:E(G)\to \{1,\dots ,k\}$)

An edge colouring assigns a label called a colour to every edge of a graph: it is a function $c:E(G)\to \{1,\dots ,k\}$. Here this definition allows arbitrary assignments. Two edges sharing a vertex may receive the same colour. A proper edge colouring imposes the additional condition that such edges receive different colours. Some textbooks use "edge colouring" as shorthand for this proper version; check the convention before applying a theorem.^[ref]

The distinction matters in Ramsey theory. In a red-blue edge colouring of a complete graph, a triangle in a graph is monochromatic when its three edges have the same colour. These are arbitrary edge colourings: forbidding equal colours on edges sharing a vertex would forbid the very monochromatic triangles in a graph being sought. For example, assigning red to every edge of $K_3$ is a valid arbitrary edge colouring, although it is not a proper edge colouring. Colour labels can also stand for time slots: then proper edge colouring turns incompatible jobs into separate rounds.

A proper edge colouring gives different labels to any two distinct edges sharing a vertex. We work with finite undirected graphs without self-loops; distinct parallel edges in a multigraph must also have different colours. For a simple graph, whose edges are two-element sets, the condition isEvery colour class $M_i=\{e\in E(G):c(e)=i\}$ is a matching in a graph. Conversely, a set partition of the edges into matchings in a graph supplies a proper edge colouring. Thus minimizing colours means grouping all the edges into as few matchings in a graph as possible.

The line graph makes the relationship with proper vertex colouring explicit: replace each original edge by a vertex, joining two new vertices exactly when their original edges share an endpoint. A proper edge colouring of $G$ becomes a proper vertex colouring of its line graph $L(G)$, so $\chi \prime (G)=\chi (L(G))$. For a multigraph, retain a distinct new vertex for each parallel edge.^[ref]

Suppose each job occupies two distinct resources for one whole slot, and each resource can serve at most one job in that slot. Make resources vertices and jobs edges. Two jobs conflict exactly when their edges share a vertex, so a valid schedule is a proper edge colouring. Each slot is a matching in a graph; the chromatic index is the minimum number of slots. The colour labels specify the slots, rather than physical colours. This model assumes all jobs are available initially, with equal duration, interchangeable slots and no additional conflicts. The school-timetable motivation in Graph Theory by Reinhard Diestel (author-hosted Colouring preview, opening paragraphs, pp. 123–124) uses this resource-pair interpretation.

Here is a complete example. Two technicians $A,B$ must each use three instruments $X,Y,Z$ once. Each job needs its technician and its instrument simultaneously. The six jobs are the edges of the complete bipartite graph $K_{2,3}$:Within each $M_i$, the two jobs use different technicians and different instruments, so $M_i$ is a matching in a graph. The three matchings in a graph together cover every job exactly once. Technician $A$ has three jobs, so fewer than three slots cannot suffice; the displayed schedule uses three. This is an optimal proper edge colouring with chromatic index three, witnessed by both a schedule and a resource-workload lower bound.

Repeated jobs requiring the same resource pair become distinct parallel edges of a multigraph, rather than one edge. Additional restrictions change the problem: prescribed allowed slots lead to list edge coloring, while unequal durations, deadlines, or jobs needing more than two resources require a richer scheduling model. Selecting a largest matching in a graph solves a single-round question; a shortest complete schedule must organize all jobs across rounds.

Each edge has a list of allowed colors; a list edge coloring chooses an allowed color on each edge, giving different colors to incident edges. The list-chromatic index is the uniform list-size threshold guaranteeing success.

The list-chromatic index is the least integer $q$ such that every assignment of at least $q$ allowed colors to each edge admits a list edge coloring. Uniform identical lists show it is at least the chromatic index. The Galvin theorem for bipartite list edge coloring gives equality for bipartite graphs.

A bipartite graph has equal list-chromatic index, chromatic index and maximum degree of a graph $\Delta$. Start with a proper $\Delta$-edge coloring. Orient its line graph toward smaller colors at one part and toward larger colors at the other. An edge of color $c$ has at most $(c-1)+(\Delta -c)=\Delta -1$ outgoing neighbours. Every induced orientation has a digraph kernel obtained from a stable matching in a bipartite graph with those preferences. Apply the kernel list-coloring lemma.

The chromatic index $\chi \prime (G)$, also called the edge chromatic number, is the least number of labels in a proper edge colouring of a finite undirected graph without self-loops. Equivalently, it is the smallest number of matchings in a graph whose set partition covers all the edges. We take $\chi \prime (G)=0$ when there are no edges. For an arbitrary edge colouring, one colour always suffices whenever an edge exists, so properness is essential to this definition. The chromatic number $\chi (G)$ instead colours vertices.^[ref]

To establish an exact chromatic index, supply both a proper edge colouring and a reason that fewer colours cannot work. Every edge at a fixed vertex must have its own colour, giving the lower bound $\chi \prime (G)\ge \Delta (G)$, where $\Delta (G)$ is the maximum degree of a graph. The bound need not be attained: it counts a single resource's workload, while conflicts can also accumulate around a graph cycle.

For the triangle in a graph $K_3$ with edges $ab,bc,ca$, every pair of edges shares a vertex, so all three require different labels. The assignment $c(ab)=1,c(bc)=2,c(ca)=3$ works, proving $\chi \prime (K_3)=3$ although $\Delta (K_3)=2$. In its line graph, those three edges become a three-vertex clique. Treating this as three pair-resource jobs makes the obstruction tangible: each resource has only two jobs, but every pair of jobs conflicts, so no slot can contain two jobs.

For the square cycle graph $C_4$ with edges $ab,bc,cd,da$, use $c(ab)=c(cd)=1$ and $c(bc)=c(da)=2$. Each colour class is a matching in a graph, and each vertex has one edge of each colour. Since $\Delta (C_4)=2$, this proves $\chi \prime (C_4)=2$. More generally, alternation closes on any even cycle graph $C_{2m}$, $m\ge 2$. On an odd cycle $C_{2m+1}$, $m\ge 1$, two-colour alternation would make the last and first edges share a colour at their common vertex; a third colour on the last edge suffices. Thus even cycle graphs have chromatic index two and odd cycle graphs have chromatic index three. These exact examples show why maximum degree of a graph alone does not determine the answer.

For every finite simple graph, Vizing's theorem givesHere $\Delta (G)$ is the maximum degree of a graph, taken as zero when there are no vertices. A bipartite graph has the stronger equality $\chi \prime (G)=\Delta (G)$. The six-job complete bipartite graph above attains this lower bound, while the triangle in a graph attains the extra-colour alternative. The simple-graph restriction in the upper bound matters.^[ref]

The bipartite graph equality still holds for finite loopless multigraphs, with parallel edges counted separately in each vertex degree. For instance, $r$ parallel jobs between two resources need exactly $r$ slots: every pair conflicts, and $\Delta =\chi \prime =r$. For a general finite loopless multigraph, however, the simple graph upper bound can fail. Put two parallel edges on each side of a triangle in a graph. All six edges pairwise share a vertex, so each needs its own colour; every vertex has degree of a vertex four. Consequently $\chi \prime =6>\Delta +1=5$. A multiplicity-aware bound is $\chi \prime (G)\le \Delta (G)+\mu (G)$, where $\mu (G)$ is the largest number of parallel edges between a pair of vertices. The doubled triangle in a graph has $\mu =2$ and attains that bound. These statements exclude self-loops; the two-distinct-resource scheduling model excludes them too.^[ref]

For historical orientation, Graph Theory by Reinhard Diestel (Colouring preview, §5.3, p. 132) dates the bipartite equality to 1916 and Vizing's theorem to 1964. These are textbook attributions; the original papers have not been inspected here. The results state existence of optimal or nearly optimal proper edge colourings, rather than saying that arbitrary greedy choices will find them. The list-chromatic index asks the further question of success for every sufficiently large family of allowed-colour lists.

A proper three-color edge coloring of a cubic graph. Label its colors by the nonzero elements of ${\mathbb{F}}_2^2$: the incident colors at each vertex then sum to zero. On a planar map without bridges in a graph, integrating these labels on the dual graph gives a four-color face coloring. On a torus, a nonzero period can obstruct this integration.