Another proof of the map color theorem for nonorientable surfaces.
type: Item
instance of: scholarly article
title: Another proof of the map color theorem for nonorientable surfaces.
zbMATH Open document ID: 1038.05018
published in: Journal of Combinatorial Theory. Series B
publication date: 2003-08-20T00:00:00Z
review text: The chromatic number \(\chi(S)\) of a surface \(S\) is the largest chromatic number of all graphs which can be embedded in the surface \(S\). The map color theorem gives the chromatic number of every (closed) surface, other than the sphere, in terms of the surface genus. The map color theorem for nonorientable surfaces (MCTN) reads as follows: If \(N_q\) is a nonorientable surface of Euler characteristic \(2-q\) then \(\chi(N_q)=\lfloor\frac{7+\sqrt{1+24q}}{2}\rfloor\) for \(q\not= 2\) and \(\chi(N_2)=6\). It is well known that to prove the MCTN it is sufficient, for every integer \(n\geq 3\), to construct an embedding of the complete graph \(K_n\) in the nonorientable surface of Euler characteristic \(2-q\), where \(q=\lceil\frac{(n-3)(n-4)}{6}\rceil\) for \(n\not= 7\) and \(q=3\) for \(n=7\). Such an embedding of \(K_n\) is called a minimal nonorientable embedding (MNE) of \(K_n\). In [\textit{G. Ringel}, Map color theorem (Springer, Berlin, etc.) (1974; Zbl 0287.05102)] the problem of construction of an MNE of \(K_n\) was solved by using the so-called current graphs (of index one, two and three) and inductive constructions. The author gives a more simple proof of MCTN using only index one current graphs and avoiding inductive constructions. In particular, for every \(n\geq 8\), \(n\not=9, 14\), the author constructs an index one current graph \(\Gamma(n)\) (with the current group \(\mathbb Z_m\)) that yields an MNE \(\psi(n)\) of \(K_n\). Moreover, the constructed current graphs have the nice property that \(\Gamma(n)\) and \(\Gamma(n+1)\) are not too different from each other. As a result, for sufficiently large \(n\), the corresponding MNE \(\psi(n)\) and \(\psi(n+1)\) have large number of common faces.
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1967946
zbMATH Keywords: embedding
zbMATH Keywords: genus of graphs
zbMATH Keywords: graph coloring
author: Vladimir P. Korzhik
MaRDI profile type: Publication
full work available at URL: jctb.2002.2124
OpenAlex ID: W2000375873
cites work: Exponential families of non-isomorphic triangulations of complete graphs
cites work: Face 2-colourable triangular embeddings of complete graphs
cites work: Surface embeddings of Steiner triple systems
cites work: Q3757929
cites work: On the number of nonisomorphic orientable regular embeddings of complete graphs
cites work: Exponential families of non-isomorphic non-triangular orientable genus embeddings of complete graphs.
cites work: Smooth solutions in case 1 of the Heawood conjecture for non-orientable surfaces
cites work: Bestimmung der Maximalzahl der Nachbargebiete auf nicht-orientierbaren Flächen
cites work: Q4773723
cites work: Remarks on the Heawood conjecture (nonorientable case)
cites work: The nonorientable genus of 𝐾_{𝑛}
DOI: 10.1006/JCTB.2002.2124
description: scientific article; zbMATH DE number 1967946