Uniquely Colorable Graphs on Surfaces

Abstract

A \(k\)-chromatic graph \(G\) is \(uniquely\) \(k\)-\(colorable\) if \(G\) has only one \(k\)-coloring up to permutation of the colors. In this paper, we focus on uniquely \(k\)-colorable graphs on surfaces. Let \({F}^2\) be a closed surface, excluding the sphere, and let \(\chi({F}^2)\) denote the maximum chromatic number of graphs embeddable on \({F}^2\). We shall prove that the number of uniquely \(k\)-colorable graphs on \({F}^2\) is finite if \(k \geq 5\), and characterize uniquely \(\chi({F}^2)\)-colorable graphs on \({F}^2\). Moreover, we completely determine uniquely \(k\)-colorable graphs on the projective plane for \(k \geq 5\).