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 F2 be a closed surface except the sphere, and let χ(F2) be the maximum number of the chromatic number of graphs which can be embedded on F2. Then we shall prove that the number of uniquely k-colorable graphs on F2 is finite if k ≥ 5, and we characterize uniquely χ(F2)-colorable graphs on F 2. Moreover, we completely determine uniquely k-colorable graphs on the projective plane, where k ≥ 5.
|Number of pages||7|
|Publication status||Published - 1 Jan 2014|