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

CREATORKengo Enami, Takahiro Matsushita
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text