Editing Graph coloring (section)

=== Scheduling ===

Vertex coloring models to a number of [[Scheduling (computing)|scheduling problems]].{{sfnp|Marx|2004}} In the cleanest form, a given set of jobs need to be assigned to time slots, each job requires one such slot. Jobs can be scheduled in any order, but pairs of jobs may be in ''conflict'' in the sense that they may not be assigned to the same time slot, for example because they both rely on a shared resource. The corresponding graph contains a vertex for every job and an edge for every conflicting pair of jobs. The chromatic number of the graph is exactly the minimum ''makespan'', the optimal time to finish all jobs without conflicts.

Details of the scheduling problem define the structure of the graph. For example, when assigning aircraft to flights, the resulting conflict graph is an [[interval graph]], so the coloring problem can be solved efficiently. In [[bandwidth allocation]] to radio stations, the resulting conflict graph is a [[unit disk graph]], so the coloring problem is 3-approximable.