Winding number and circular coloring
Reza Naserasr, Cyril Pujol, Lujia Wang · 2026
Read Winding number and circular coloring by Reza Naserasr, Cyril Pujol, Lujia Wang (2026) 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-2606-25644.txt.
Introduction
Colouring a graph drawn on a surface can hit forbidden values. A famous theorem says four sided faces on the projective plane never need exactly three colours. Reza Naserasr, Cyril Pujol, and Lujia Wang unify such gaps in 2026 through winding numbers. A winding number measures how a colouring wraps around cycles when extended to a continuous map. Their framework covers circular colourings, a finer colour measure. It also handles faces of one fixed odd length, settled before only for triangles.
Signed graphs, whose edges carry plus or minus marks, join the theory through a link with vertex switching. New forbidden bands follow. On the projective plane, positive faced signed graphs skip one band of values, and negative faced ones skip another. A construction with arbitrary negative girth shows the signed world is richer. In the unsigned case, the complete graph on six vertices stands alone.
Catalog record
| CREATOR | Reza Naserasr, Cyril Pujol, Lujia Wang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 98 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.25644
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Winding number and circular coloring Reza Naserasr, Cyril Pujol, Lujia Wang Abstract In 1996, Youngs proved a surprising theorem that quadrangulations of the projective plane could never have chromatic number exactly 3. This sparked a lot of interest, and the result has been further developed in many directions over the past decades. For example, the result is strengthened by considering the circular chromatic number, which is a real-valued lower bound on the chromatic number: The circular chromatic number of a quadrangulation cannot be in the interval ( 2 , 4 ) (2,4) . This parameter allows a generalization to larger even faces, for which a similar gap exists. In this work, we place these results into a framework based on the notion of winding number using extensions of colorings to continuous mappings.This yields unified and simplified proofs of gaps in the circular chromatic number for graphs with a distinguished set of directed even cycles. This generalizes the setting of graphs embedded on surfaces where every face is even. We further establish an analogous gap phenomenon when all faces are of a given odd length, previously known only in the case of triangulations. For example, we conclude that if G G is a graph embedded on the projective plane such that all faces are 5-cycles, then either its circular chromatic number is 5 2 \frac{5}{2} or at least 3 3 , the former being the case only if G G is Eulerian and every noncontractible facial walk is of odd length. We then extend this framework to signed graphs, where the analogy between vertex switching and ℤ 2 \mathbb{Z}_{2} -actions provides a natural topological setting. We show that given a circular r r -coloring ϕ \phi of a signed graph, where r r is relatively small, a specific continuous extension of ϕ \phi over the signed graph, viewed as a topological object, must satisfy certain requirements. This translates to lower bounds on the circular chromatic number of certain families of signed graphs. In particular, we show that the circular chromatic number of a signed graph embedded on the projective plane whose faces all have length k k cannot be in the interval ( 2 , 2 k k − 2 ) (2,\frac{2k}{k-2}) if the faces are positive, nor in the interval ( 2 k k − 1 , 2 k − 2 k − 2 ) (\frac{2k}{k-1},\frac{2k-2}{k-2}) if the faces are negative. Applying this on signed triangulations of the projective plane where facial cycles are all positive, we conclude that any such signed graph is either balanced or has circular chromatic number 6. It is observed that this easily implies the aforementioned result for quadrangulations. For any positive integer k k , we construct a triangulation of the projective plane where each face is a positive triangle and the negative girth is k k . This is in contrast with the (unsigned) graph case since K 6 K_{6} is the only 6-critical graph embedded on the projective plane and, moreover, C. Thomassen proved that there are only finitely many 6-critical graphs on any given surface. 1 Introduction In the 1990s, several results of similar nature were produced by independent groups of researchers. Extending topological methods, Stiebitz, after introducing generalized Mycielskian (also known as the cone cover), proved in [ 22 ] that if a graph is obtained from K_{2} by repeatedly applying generalized Mycielski construction, then at each step its chromatic number is increased by 1. Although the original result is not accessible, the key ideas appear in [ 5 ] . Studying 4-chromatic graphs of large odd girth, Van Ngoc and Tuza introduced M_{k}(C_{2k+1}) as potentially the smallest 4-chromatic graph of odd girth 2k+1 , this remains an open problem until now. Studying quadrangulations of the projective plane, Youngs proved in [ 27 ] that such graphs are never 3-chromatic. Prior to Youngs result, Payan, in [ 21 ] proved a similar statement that cube-like graphs (Cayley graphs on binary groups) are never 3-chromatic. We refer to Section 5 for details on these families, but we note that M_{k}(C_{2k+1}) can be embedded on the projective plane as a quadrangulation. They are also the 4-chromatic graphs that Payan identified in [ 21 ] as 4-chromatic subgraphs of non-bipartite cube-like graphs (see also [ 1 ] ). These results have been strengthened and extended in numerous ways in the past 3 decades from various points of view. Among others, results of [ 12 ] and [ 2 ] are of special interest as we further extend their view points. Here we put these families of results in a larger setting and among other things, we propose extensions to signed graphs. Our follow up work shows that the application of algebraic topology to graph coloring is in fact better suited for extended notions of coloring based on the language of signed graphs. That is because of the analogy between \mathbb{Z}_{2} -actions on topological spaces (that are essential elements of connection to coloring) and vertex switching operation in signed graphs. For standard notion of graph theory we follow [ 26 ] . We settle our choice of terminology for signed graphs in the following subsection, referring to [ 15 , 16 ] for more. Formalizing the notion of winding number is done in Section 1.2 . In Section 2 we study general properties of winding number for graphs. We apply the development to prove lower bounds on the circular chromatic number of graphs in Section 3 . Winding number for signed graphs together with application on the circular chromatic number is considered in Section 4 . Special classes of signed graphs, which are candidate to be the smallest signed graphs of the given negative girth and circular chromatic number, are presented in Section 5 . 1.1 Signed graphs A signed graph (G,\sigma) is a graph G together with an assignment \sigma of signs ( + or - ) to its edges. The sign of a closed walk in (G,\sigma) is the product of signs of its edges considering multiplicity. A signed graph (or a subset of its vertices) is said to be balanced if it induces no negative cycle. Switching a vertex v means multiplying the sign of each incident edge by a - . A key property in the study of signed graphs is that switching a vertex does not impact the signs of closed walks and cycle. The balanced chromatic number of a signed graph (G,\sigma) , denoted \chi_{b}(G,\sigma) , is the minimum number of balanced sets which covers V(G) . 1.2 Winding number The winding number is an algebraic notion used in topology in order to distinguish closed curves that cannot continuously be transformed to one another. In intuitive terms, for a continuous function from S^{1} to S^{1} the winding number counts how many times the first, as a curve, “winds around the circle”. For example in Figure 1 the blue curve winds around the black circle twice. Depending on whether the wrapping around the circle is done in the clockwise direction or counterclockwise, the winding number is positive or negative, noting that the opposite directions cancel each other out. Figure 1: Example of a curve with winding