Uniquely colorable graphs on surfaces

Naoki Matsumoto, Kenta Noguchi

Research output: Contribution to journalArticle

1 Citation (Scopus)

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 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.

Original languageEnglish
Pages (from-to)177-183
Number of pages7
JournalArs Combinatoria
Volume114
Publication statusPublished - 1 Jan 2014

    Fingerprint

Cite this