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\ge 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\ge 5$.