Another proof of the map color theorem for nonorientable surfaces. (Q1403919): Difference between revisions

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.