The Number of \(1\)-Factors and Edge-Colorings of Médbius Ladder Graphs and Triangular Embeddings of \(K_{12m+7}\)

Abstract

In this paper, we study the number of 1-factors and edge-colorings of the Möbius ladder graphs. We find exact formulae for such numbers and show that there are exponentially many 1-factors and edge-colorings in such graphs. As applications, we show that every “man-made” triangular embedding for \(K_{12m+7}\), by combining the current graphs with those of Youngs and Ringel, permits exponentially many “Grünbaum colorings” (i.e., 3-edge-colored triangulations in such a way that each triangle receives three distinct colors).