Edge coloring lattice graphs

Understand

We develop the theory of the edge coloring of infinite lattice graphs, proving a necessary and sufficient condition for a proper edge coloring of a patch of a lattice graph to induce a proper edge coloring of the entire lattice graph by translation.

• This condition forms the cornerstone of a method that finds nearly minimal or minimal edge colorings of infinite lattice graphs.
• In case a nearly minimal edge coloring is requested, the running time is $O(\mu^2 D^4)$, where $\mu$ is the number of edges in one cell (or `basis graph') of the lattice graph and $D$ is the maximum distance between two cells so that there is an edge from within one cell to the other.
• In case a minimal edge coloring is requested, we lack an upper bound on the running time, which we find need not pose a limitation in practice; we use the method to minimal edge color the meshes of all $k$-uniform tilings of the plane for $k\leq 6$, while utilizing modest computational resources.