Simple vertex coloring algorithms

Jackson Morris, Fang Song

Given a graph $G$ with $n$ vertices and maximum degree $\Delta$, it is known that $G$ admits a vertex coloring with $\Delta +1$ colors such that no edge of $G$ is monochromatic. This can be…