Higher-dimensional generalization of Youngs’ theorem and circular colorings
Kengo Enami, Takahiro Matsushita · 2025
Read Higher-dimensional generalization of Youngs’ theorem and circular colorings by Kengo Enami, Takahiro Matsushita (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-23562.txt.
Introduction
Kengo Enami and Takahiro Matsushita extend a classic result on coloring maps drawn on odd surfaces. In 1996, Youngs showed that a certain tiling of the projective plane can never be colored with three colors. Later work stretched that claim to other surfaces, higher dimensions, and circle-based color schemes. Their 2025 work gives one broad claim that yields many of those stretches at once.
Catalog record
| CREATOR | Kengo Enami, Takahiro Matsushita |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-23562
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Higher-dimensional generalization of Youngs’ theorem and circular colorings Kengo Enami, Takahiro Matsushita Abstract . In 1996, Youngs proved that any quadrangulation of the real projective plane is not 3 3 -chromatic. This result has been extended in various directions over the years, including to other non-orientable closed surfaces, higher-dimensional analogues of quadrangulations and circular colorings. In this paper, we provide a generalization which yields some of these extensions of Youngs’ theorem. 2020 Mathematics Subject Classification Primary 05C15; Secondary 05C10 1. Introduction 1.1. Youngs’ theorem Quadrangulations on surfaces have been extensively studied in topological graph theory. The purpose of this paper is to provide a generalization of a theorem by Youngs (Theorem 1.1 ) concerning the graph coloring problem of quadrangulations on the real projective plane. In this paper, every graph is assumed to be simple. A surface means a compact connected 2 -dimensional manifold, possibly with boundary. An embedded graph G on a surface S is said to be cellular if every face is homeomorphic to a 2 -cell. A cellular embedding is said to be even-sided if every face is bounded by a closed walk of even length. In particular, if every face is bounded by a closed walk of length 4 , the embedding is called a quadrangulation . Graph coloring problems are one of the central topics in topological graph theory. For plane graphs, the Four Color Theorem [ 2 , 3 , 4 ] serves as a cornerstone result. For graphs embedded on non-spherical closed surfaces, the Map Color Theorem [ 12 ] is a natural extension of the four color theorem, which states that every graph embedded on a non-spherical closed surface S with Euler characteristic \varepsilon(S) has chromatic number \chi(G)\leq\left\lfloor\frac{7+\sqrt{49-24\varepsilon(S)}}{2}\right\rfloor. This bound was later shown to be best possible for all closed surfaces except for the Klein bottle, through the work of Ringel and Youngs [ 25 ] . These foundational results have inspired a vast body of subsequent research. In addition to these developments, coloring problems for graphs with even-sided embeddings have also received attention. It is easy to see that a graph cellularly embedded on the sphere is 2 -colorable if and only if the embedding is even-sided. On the other hand, Hutchinson [ 14 ] showed that every graph G that admits an even-sided embedding on a non-spherical closed surface S has chromatic number \chi(G)\leq\dfrac{5+\sqrt{25-16\varepsilon(S)}}{2}. Later, Liu et al. [ 19 ] proved that this bound is best possible for all closed surfaces except for the Klein bottle and the double torus. In the case of a quadrangulation G on the projective plane, the above inequality implies that \chi(G)\leq 4 . On the other hand, Youngs proved the following landmark result. Theorem 1.1 (Youngs [ 28 ] ) . Any quadrangulation of the real projective plane \mathbb{R}P^{2} is not 3 -chromatic. Hence the chromatic number of a quadrangulation of a real projective plane is 2 or 4 . This phenomenon is remarkable since 3 -chromatic quadrangulations exist for all other non-spherical closed surfaces. Moreover, Hutchinson [ 15 ] showed that every graph with an even-sided embedding on any orientable closed surface in which every non-contractible cycle is sufficiently long is 3 -colorable. Youngs’ theorem and its extension to non-orientable closed surface mentioned below (Theorem 1.2 ) indicate that this does not hold for non-orientable closed surfaces. 1.2. Various generalizations and refinements There are various extensions of Youngs’ theorem, and our main theorem (Theorem A ) is a generalization of Youngs’ theorem, which yields some of them. First, we discuss the extension of Youngs’ theorem to non-orientable closed surfaces, which was independently established by Archdeacon et al. [ 5 ] and Mohar and Seymour [ 23 ] . Theorem 1.2 (Archdeacon et al. [ 5 ] and Mohar and Seymour [ 23 ] ) . Let N be a closed non-orientable connected surface, and G a quadrangulation of N . Suppose that G has an odd cycle C such that the surface obtained by cutting N along C is orientable. Then G is not 3 -chromatic. Next we discuss a higher-dimensional generalization of Youngs’ theorem. Hachimori, Nakamoto and Ozeki [ 10 ] considered d -dimensional quadrangulations of the real d -dimensional projective space \mathbb{R}P^{d} for any d\geq 2 as follows: Set I=[0,1] and consider the standard CW structure of I^{n} . A regular CW complex C is called a cubical complex if each characteristic map \varphi\colon I^{n}\to C of an n -cell of C is a cellular embedding, that is, \varphi(I^{n}) is a subcomplex of C and \varphi is an isomorphism between I^{n} and \varphi(I^{n}) . If a cubical complex C is homeomorphic to a topological space X , then the 1-skeleton of C is called a quadrangulation of X . Hachimori, Nakamoto and Ozeki [ 10 ] proved that for all d\geq 2 , any d -dimensional quadrangulation of the real projective space \mathbb{R}P^{d} satisfying a certain geometric condition is 2 - or 4 -chromatic. They further asked whether this geometric condition is necessary; that is, whether every non-bipartite d -dimensional quadrangulation of \mathbb{R}P^{d} is necessarily 4 -chromatic. Recently, Kaiser et al. [ 16 ] announced a negative answer to this question by constructing 3 -dimensional quadrangulations of \mathbb{R}P^{3} with arbitrarily large chromatic numbers. Nevertheless, they also established the following theorem, which shows that Youngs’ result does extend to higher dimensions under certain conditions. Theorem 1.3 (Kaiser et al. [ 16 ] ) . For all d\geq 2 , every d -dimensional quadrangulation of the real projective space \mathbb{R}P^{d} is not 3 -chromatic. Another type of higher-dimensional generalization of Youngs’ theorem was discussed in Kaiser and Stehlík [ 17 ] . Finally, we discuss a refinement of Youngs’ theorem from the perspective of circular chromatic numbers. The circular chromatic number \chi_{c}(G) is a real-valued invariant of a graph G satisfying \lceil\chi_{c}(G)\rceil=\chi(G) . In this sense, \chi_{c}(G) refines the chromatic number, and has been extensively studied. We refer the reader to [ 24 , 29 , 30 ] for surveys on this concept. The precise definition of the circular chromatic number will be given in Subsection 5.1 . DeVos et al. [ 7 ] proved the following refinement of Youngs’ theorem. Theorem 1.4 (DeVos et al. [ 7 ] ) . Let G be a non-bipartite graph with an even-sided embedding on \mathbb{R}P^{2} . Let k be a positive integer such that every face of G is 2i -gon with i\leq k . Then \chi_{c}(G)\geq 2+\frac{2}{k-1}. 1.3. Results The goal of this paper is to present a generalization of Youngs’ theorem that yields Theorems 1.2 , 1.3 and 1.4 . Before stating the main theorem, we define a class of CW complexes. Let X be a CW complex satisfying the following conditions: (1) The 1 -skeleton X^{1} of X is a simple graph. (2) The attaching map of each 2 -cell of X is a graph homomorphism C_{2r}\to X^{1} for some r\geq 2 . In this case, we say that X is a CW complex with even 2 -skeleton . When the attaching map of every 2 -cell is a graph homomorphism from C_{4} , we say that X is a CW complex with quadrangulated 2 -skeleton . Note that a cubical