TY - JOUR
T1 - Chromatic Numbers and Cycle Parities of Quadrangulations on Nonorientable Closed Surfaces
AU - Nakamoto, Atsuhiro
AU - Negami, Seiya
AU - Ota, Katsuhiro
N1 - Copyright:
Copyright 2007 Elsevier B.V., All rights reserved.
PY - 2002/7
Y1 - 2002/7
N2 - In this paper, we shall show that every quadrangulation on a nonorientable closed surface with sufficiently large representativity has chromatic number 2, 3 or 4 and characterize those for each value, discussing an algebraic invariant called a cycle parity. In particular, we shall prove that such a quadrangulation is 4-chromatic if and only if it has an odd cycle which cuts open the host surface into an orientable surface.
AB - In this paper, we shall show that every quadrangulation on a nonorientable closed surface with sufficiently large representativity has chromatic number 2, 3 or 4 and characterize those for each value, discussing an algebraic invariant called a cycle parity. In particular, we shall prove that such a quadrangulation is 4-chromatic if and only if it has an odd cycle which cuts open the host surface into an orientable surface.
UR - http://www.scopus.com/inward/record.url?scp=34247117966&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34247117966&partnerID=8YFLogxK
U2 - 10.1016/S1571-0653(04)00096-4
DO - 10.1016/S1571-0653(04)00096-4
M3 - Article
AN - SCOPUS:34247117966
SN - 1571-0653
VL - 11
SP - 509
EP - 518
JO - Electronic Notes in Discrete Mathematics
JF - Electronic Notes in Discrete Mathematics
ER -