Edge coloring lattice graphs

Abstract

We develop the theory of the edge coloring of lattice graphs. A central role is played by 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. Using this condition, we introduce a method that finds nearly minimal or minimal edge colorings of lattice graphs. For a nearly minimal edge coloring, the running time is O(μ2D4), where μ is the number of edges in one cell (or “basis graph”) of the lattice graph and D is the maximum distance between two cells connected by an edge. Crucially, this complexity depends only on local properties of the lattice graph, making it independent of the total graph size. As a result, the method applies even to infinite lattice graphs with finite maximum degree. For minimal edge coloring, we lack a rigorous upper bound on the running time, which we find poses no limitation in practice; we use the method to minimally edge color the meshes of all k-uniform tilings of the plane for k ≤ 6 with modest computational resources. We find that all these lattice graphs belong to Vizing class I. By relating edge colorings to quantum circuits, our work has direct applications in quantum computation, including quantum simulation of condensed matter, cluster-state preparation, error characterization, and error correction.