Lovász Toggle

Let $G=(V,E)$ be a graph with maximal degree $\Delta$. Let $r,b$ be positive integers such that $\Delta\leq r+b+1$. Does there exist a coloring of the vertices red and blue such that

(i)

every red vertex has at most $r$ red neighbors; and

(ii)

every blue vertex has at most $b$ blue neighbors.

Theorem 3.1 (Lovász)   A coloring satisfying (i) and (ii) always exists.

Lovász proved this theorem by showing that the following algorithm always terminates. We call a vertex bad (with respect to the current red/blue coloring) if it violates (i) or (ii).

Procedure ``Lovász toggle''

Start from an arbitrary red/blue coloring of the vertices.

while a bad vertex exists,

pick a bad vertex and recolor it. end (while )