Threshold-Coloring of Archimedean and Laves Lattices.
Md. Jawaherul Alam, Stephen Kobourov, Sergey Pupyrev, Jackson Toeniskoetter · arXiv (Cornell University) · 2013
We study threshold-coloring of tilings of the plane by regular polygons, known as Archimedean lattices. We prove that some are threshold-colorable with constant number of colors while some require $O(\sqrt n)$ colors for a lattice of $n$ vertices. Using a threshold-coloring we can construct unit-cube contact representation for the colorable Archimedean lattices and any sublattice thereof. We show that sparse and high girth planar graphs are $(5,1)$-total-threshold-colorable.