= Edge coloring as scheduling
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}$:
$$
E=\{AX,AY,AZ,BX,BY,BZ\},\qquad
M_1=\{AX,BY\},\quad M_2=\{AY,BZ\},\quad M_3=\{AZ,BX\}.
$$
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.
\Image[/edge-coloring-bipartite-job-slots.png]
{title=Six jobs on a <complete bipartite graph> become three scheduling slots, each a <matching in a graph>}
{description=The <vertices> are resources, and each numbered <edge> is one job. The slot table uses the same colour labels as the <proper edge colouring>. A technician or instrument appears at most once within a column. Crossings of drawn <edges> introduce no resource and no conflict.}
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.
Back to article page
