Edge-Bandwidth of the Triangular Grid

Reza Akhtar, Tao Jiang, Dan Pritikin


In 1995, Hochberg, McDiarmid, and Saks proved that the vertex-bandwidth of the triangular grid $T_n$ is precisely $n+1$; more recently Balogh, Mubayi, and Pluhár posed the problem of determining the edge-bandwidth of $T_n$. We show that the edge-bandwidth of $T_n$ is bounded above by $3n-1$ and below by $3n-o(n)$.

Full Text: