## Projekt: Branch- and Bound Algorithmen für das equitable Graphenfärbungsproblem

Förderung: DFG Exellence Initiative
Lehrstuhl II für Mathematik, Lehr- und Forschungsgebiet Diskrete Optimierung
RWTH Aachen University

Overview / The equitable coloring problem / Code and Data /

## The equitable coloring problem

### Graph coloring

Given an undirected graph ${\small G(V,E)}$, the graph coloring problem asks for
• the minimal integer ${\small k\in\mathbb{Z}_+}$,
• such that there is map (the coloring) ${\small f:V\rightarrow\{1,\ldots,k\}:\;v\mapsto f(v)}$
• with ${\small f(v)\neq f(w)\quad \forall\;vw\in E }$.

### Applications:

• Assigning workers (colors) to conflicting jobs.
• Assigning maschines (colors) to conflicting tasks.

### Equitable coloring

We consider an extension of the graph coloring problem. We ask whether there is a coloring, that is a function f, with the additional properties that
• the sizes of the color classes may only differ by one, i.e.,
• ${\small \left| \left| \{v \mid f(v)=j\} \right| - \left| \{v \mid f(v)=i\} \right| \right| \leq 1 \quad \forall\;i,j\in\{1,\ldots,k\}}$.
• In other words: each worker has at most one more task than any other worker.

### Algorithmic approach: DSATUR

Enummerate all possible equitable colorings in a tree-like structure. Branching and Bounding where possible.
• Only minor differences to DSATUR for 'standard' coloring.
• Within the algorithm, node and color selection is not trivial.
• Pruning is extremely important.
Compare the example in Figure 2. On the left, the tree-like enummeration of the colorings, on the right, the corresponding graph coloring.