Chromatic numbers of quadrangulations on closed surfaces

Dan Archdeacon, Joan Hutchinson, Atsuhiro Nakamoto, Seiya Negam, Katsuhiro Ota

研究成果: Article査読

30 被引用数 (Scopus)


It has been shown that every quadrangulation on any non-spherical orientable closed surface with a sufficiently large representativity has chromatic number at most 3. In this paper, we show that a quadrangulation G on a nonorientable closed surface Nk has chromatic number at least 4 if G has a cycle of odd length which cuts open Nk into an orientable surface. Moreover, we characterize the quadrangulations on the torus and the Klein bottle with chromatic number exactly 3. By our characterization, we prove that every quadrangulation on the torus with representativity at least 9 has chromatic number at most 3, and that a quadrangulation on the Klein bottle with representativity at least 7 has chromatic number at most 3 if a cycle cutting open the Klein bottle into an annulus has even length. As an application of our theory, we prove that every nonorientable closed surface Nk admits an eulerian triangulation with chromatic number at least 5 which has arbitrarily large representativity.

ジャーナルJournal of Graph Theory
出版ステータスPublished - 2001 6月

ASJC Scopus subject areas

  • 幾何学とトポロジー


「Chromatic numbers of quadrangulations on closed surfaces」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。