pith. sign in

arxiv: 2606.25644 · v1 · pith:ZYGHIZMKnew · submitted 2026-06-24 · 🧮 math.CO

Winding number and circular coloring

Reza Naserasr , Cyril Pujol , Lujia Wang This is my paper

Pith reviewed 2026-06-25 20:42 UTC · model grok-4.3

classification 🧮 math.CO
keywords circular chromatic numberwinding numberprojective planegraph embeddingfacial cyclesodd faceseven cycles
0
0 comments X

The pith

Graphs embedded on the projective plane with every face a 5-cycle have circular chromatic number either 5/2 or at least 3.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that circular chromatic numbers of graphs with uniform face lengths on surfaces exhibit gaps. It extends discrete colorings to continuous maps on the surface and tracks the winding number around distinguished directed cycles, which must remain an integer. This unifies earlier gap results for even faces, such as the absence of values in (2,4) for quadrangulations, and extends the method to odd face lengths. For 5-cycles on the projective plane the circular chromatic number therefore lands at 5/2 or jumps to at least 3, with 5/2 possible only when the graph is Eulerian and every noncontractible facial walk has odd length.

Core claim

If G is embedded on the projective plane with every face a 5-cycle, then its circular chromatic number is either 5/2 or at least 3, the former holding only if G is Eulerian and every noncontractible facial walk has odd length. The same winding-number argument yields gaps for graphs with any distinguished set of directed even cycles and for other uniform odd face lengths.

What carries the argument

The winding number of a continuous extension of a coloring around each distinguished directed cycle or odd facial walk, which is forced to be an integer.

If this is right

  • Even-faced embeddings on surfaces have circular chromatic numbers avoiding the open interval (2,4).
  • For (2k+1)-face embeddings on the projective plane the circular chromatic number avoids the interval (k/2,k) under the stated Eulerian and parity conditions.
  • The gap method applies directly to any graph equipped with a distinguished collection of directed even cycles.
  • The same integer-winding constraint produces analogous gaps when all faces have any fixed odd length.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The framework could be applied to embeddings on the torus or Klein bottle to obtain new gap statements.
  • The result implies that the ordinary chromatic number is at least 3 for any such 5-face projective-plane graph that fails the Eulerian or odd-walk conditions.
  • Explicit constructions of 5-face Eulerian embeddings with odd noncontractible walks would test whether 5/2 is attained.
  • The winding-number technique may extend to graphs whose distinguished cycles are not facial.

Load-bearing premise

Any coloring that uses a number of colors inside the forbidden gap interval extends to a continuous map on the surface while keeping the winding number integer on every distinguished cycle.

What would settle it

An explicit 5-face embedding on the projective plane that is not Eulerian or has an even-length noncontractible walk yet possesses a circular chromatic number strictly between 5/2 and 3.

Figures

Figures reproduced from arXiv: 2606.25644 by Cyril Pujol, Lujia Wang, Reza Naserasr.

Figure 1
Figure 1. Figure 1: Example of a curve with winding number 2 [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Shortest (left) and clockwise (right) extension of an edge [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of the proof, focussing on a 4-cycle [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: For each positioning of the four colors on [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Quadrangulations of the projective plane with even (left) and odd (right) noncontractible cycles. [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: An eulerian projective planar graph, with a negative face walk [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: A 4-chromatic triangulation of the Klein bottle together with an orientation of the faces, whose [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Shortest (left) and clockwise (right) extension of a positive and negative edge [PITH_FULL_IMAGE:figures/full_fig_p014_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Continuous extension of signed cycles with shortest conventions and impact of switching [PITH_FULL_IMAGE:figures/full_fig_p015_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Pℓ ˆ pC2k`1q [PITH_FULL_IMAGE:figures/full_fig_p019_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: MlpC2k`1q in the face after which all the resulting faces are 4-cycles. In [PITH_FULL_IMAGE:figures/full_fig_p019_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: M3pC7q In [24] (see also [19]), the graphs MkpC2k`1q are introduced as the potentially the smallest 4-chromatic graphs of odd girth at least 2k ` 1. Noting that MkpC2k`1q has 2k 2 ` k ` 1 vertices, a lower bound of pk ´ 1q 2 is proved on the order of such graphs in [8]. The proof is a basic modification of [20] where a lower bound of pk´1q 2 2 was proved. For the subclass of 4-chromatic projective planar … view at source ↗
Figure 13
Figure 13. Figure 13: Bipartite analogue [PITH_FULL_IMAGE:figures/full_fig_p020_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: for a specific example [PITH_FULL_IMAGE:figures/full_fig_p020_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: M3pC8q Our next construction is based on Pℓ ˆ C2k to which we add a new vertex, say u, joined to all 2k vertices of the first layer. Viewing the graph on the plane with a natural embedding, where u is in the center, the outer face is a 4k-cycle. Connecting antipodal vertices of this cycle through a cross cap we get a quadrangulation of the projective plane whose odd girth is the mint2l ` 1, 2k ` 1u, as it… view at source ↗
Figure 16
Figure 16. Figure 16: BM{ℓpC2kq [PITH_FULL_IMAGE:figures/full_fig_p022_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: BM{4pC8q edges. In Figures 19 to 21 we have best possible examples of girth 3, 4, and 5. In conclusion, for every integer k, there is a positive triangulation of the projective plane whose negative girth is at least k. Thus in particular we have infinitely many inclusion-wise minimal signed simple graphs embedded on the projective plane whose circular chromatic number is 6. This is in contrast with the gr… view at source ↗
Figure 18
Figure 18. Figure 18: A triangulation based on BM4pC7q whose negative girth is 7. A lower bound on the number of vertices of a 6-chromatic signed graph of negative girth at least k is implied in [25]. Further improvement together with a proof that some of the construction presented here are critical, meaning their circular chromatic number drops to 4 by removal of any edge, would be addressed in a forthcoming work [PITH_FULL_… view at source ↗
Figure 19
Figure 19. Figure 19: A positive triangulation with negative girth 3 [PITH_FULL_IMAGE:figures/full_fig_p023_19.png] view at source ↗
Figure 20
Figure 20. Figure 20: A positive triangulation of negative girth 4 [PITH_FULL_IMAGE:figures/full_fig_p024_20.png] view at source ↗
Figure 21
Figure 21. Figure 21: A positive triangulation of negative girth 5 [PITH_FULL_IMAGE:figures/full_fig_p024_21.png] view at source ↗
read the original 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). 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 is a graph embedded on the projective plane such that all faces are 5-cycles, then either its circular chromatic number is 5/2 or at least 3, the former being the case only if G is Eulerian and every noncontractible facial walk is of odd length...

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper develops a topological framework based on winding numbers obtained by extending discrete circular colorings to continuous maps on surfaces. It uses this to give unified proofs of gaps in the circular chromatic number for graphs with distinguished directed even cycles (generalizing quadrangulations and even-face embeddings) and establishes an analogous gap for embeddings where all faces are odd cycles of fixed length. The main new result is that a graph embedded on the projective plane with every face a 5-cycle has circular chromatic number either exactly 5/2 or at least 3, with the former case holding only when the graph is Eulerian and every noncontractible facial walk has odd length.

Significance. If the extension construction is shown to preserve the required integer winding numbers on the distinguished cycles, the work supplies simplified, topology-based proofs of several known gap results and extends the gap phenomenon to odd-face embeddings on surfaces, a setting previously limited to triangulations. The approach is parameter-free and relies on standard winding-number invariants rather than ad-hoc constructions.

major comments (2)
  1. [the extension construction used in the proof of the 5-cycle projective-plane statement] The continuous-extension step (the construction that produces a map from a discrete (5/2)-coloring to a continuous map on the surface) is load-bearing for the “only if” direction of the projective-plane 5-cycle theorem. The manuscript must explicitly verify that this extension forces the winding number on every noncontractible odd-length facial walk to remain an integer; without that verification the gap argument does not rule out values in (5/2,3).
  2. [the general odd-face gap theorem] The general framework for odd-length faces invokes the same extension to obtain an integer winding-number obstruction. The argument that the obstruction is forced for every distinguished directed cycle (or odd facial walk) when the coloring value lies in (k/2,(k+1)/2) needs a self-contained lemma showing that any continuous extension compatible with the discrete coloring cannot alter the integrality on those cycles.
minor comments (2)
  1. Notation for the target circle and the identification of colorings with maps to S^1 should be introduced once and used consistently; the current alternation between interval and circle descriptions is occasionally unclear.
  2. A short diagram illustrating the extension of a discrete coloring across a single face would help readers follow the winding-number calculation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The two major comments correctly identify places where the manuscript's treatment of the continuous-extension construction requires additional explicit verification to make the gap arguments fully rigorous. We will revise the paper accordingly.

read point-by-point responses

  1. Referee: [the extension construction used in the proof of the 5-cycle projective-plane statement] The continuous-extension step (the construction that produces a map from a discrete (5/2)-coloring to a continuous map on the surface) is load-bearing for the “only if” direction of the projective-plane 5-cycle theorem. The manuscript must explicitly verify that this extension forces the winding number on every noncontractible odd-length facial walk to remain an integer; without that verification the gap argument does not rule out values in (5/2,3).

    Authors: We agree that the current write-up does not contain a self-contained verification of integrality preservation for noncontractible odd-length facial walks under the extension map. In the revised manuscript we will insert a new lemma (placed immediately before the projective-plane 5-cycle theorem) that constructs the extension explicitly from the discrete (5/2)-coloring and proves that the induced winding numbers on all noncontractible odd facial walks remain integers. This will close the gap in the “only if” direction. revision: yes

  2. Referee: [the general odd-face gap theorem] The general framework for odd-length faces invokes the same extension to obtain an integer winding-number obstruction. The argument that the obstruction is forced for every distinguished directed cycle (or odd facial walk) when the coloring value lies in (k/2,(k+1)/2) needs a self-contained lemma showing that any continuous extension compatible with the discrete coloring cannot alter the integrality on those cycles.

    Authors: We concur that a general, self-contained lemma is needed rather than an implicit appeal to the construction. The revision will add a standalone lemma (in the section developing the general odd-face framework) that takes an arbitrary discrete coloring with value in (k/2,(k+1)/2) and any continuous extension compatible with it, and proves that the winding numbers on the distinguished directed cycles (or odd facial walks) remain integers. The lemma will be stated and proved independently of the specific surface or face length, so that it applies uniformly to both the even-cycle and odd-face settings. revision: yes

Circularity Check

0 steps flagged

No significant circularity; standard topological framework

full rationale

The paper develops a winding-number framework via continuous extensions of discrete colorings to prove circular-chromatic gaps for even-face and odd-face embeddings on surfaces. All load-bearing steps invoke externally defined topological invariants (winding numbers on cycles) and standard extension constructions rather than any parameter fitted inside the paper or any self-referential definition. The central 5/2-vs-3 gap for projective-plane 5-cycle embeddings is derived from these invariants applied to noncontractible walks; no equation or claim reduces by construction to its own inputs, and no load-bearing self-citation chain is present. The derivation remains self-contained against external topological benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the topological properties of winding numbers under continuous extensions and on the standard definition of circular chromatic number; no free parameters or invented entities appear in the abstract.

axioms (1)
  • domain assumption A proper vertex coloring of a graph embedded on a surface extends to a continuous map whose winding number around each distinguished directed cycle is an integer.
    Invoked to obtain the gap from the parity or integrality of the winding number.

pith-pipeline@v0.9.1-grok · 5771 in / 1170 out tokens · 39704 ms · 2026-06-25T20:42:06.592682+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references

  1. [1]

    Homomorphisms of binary Cayley graphs.Dis- crete Math., 338(12):2539–2544, 2015

    Laurent Beaudou, Reza Naserasr, and Claude Tardif. Homomorphisms of binary Cayley graphs.Dis- crete Math., 338(12):2539–2544, 2015

    2015

  2. [2]

    Coloring-flow duality of embedded graphs.Trans

    Matt DeVos, Luis Goddyn, Bojan Mohar, Dirk Vertigan, and Xuding Zhu. Coloring-flow duality of embedded graphs.Trans. Amer. Math. Soc., 357(10):3993–4016, 2005

    2005

  3. [3]

    El-Zahar and N

    M. El-Zahar and N. W. Sauer. The chromatic number of the product of two 4-chromatic graphs is 4. Combinatorica, 5:121–126, 1985

    1985

  4. [4]

    The width of quadrangulations of the projective plane.J

    Louis Esperet and Matˇ ej Stehl´ ık. The width of quadrangulations of the projective plane.J. Graph Theory, 89(1):76–88, 2018

    2018

  5. [5]

    On graphs with strongly independent color- classes.J

    Andr´ as Gy´ arf´ as, Tommy Jensen, and Michael Stiebitz. On graphs with strongly independent color- classes.J. Graph Theory, 46(1):1–14, 2004

    2004

  6. [6]

    P. J. Heawood. On the four colour map theorem.Quart. J., 29:270–285, 1898

  7. [7]

    Bruce Richter, and Paul Seymour

    Joan Hutchinson, R. Bruce Richter, and Paul Seymour. Colouring Eulerian triangulations.J. Comb. Theory, Ser. B, 84(2):225–239, 2002

    2002

  8. [8]

    Small odd cycles in 4-chromatic graphs.J

    Tao Jiang. Small odd cycles in 4-chromatic graphs.J. Graph Theory, 37(2):115–117, 2001

    2001

  9. [9]

    Andrea Jim´ enez, Jessica McDonald, Reza Naserasr, Kathryn Nurse, and Daniel A. Quiroz. Balanced chromatic number and hadwiger-like conjectures

  10. [10]

    Circular flows in mono-directed signed graphs.J

    Jiaao Li, Reza Naserasr, Zhouningxin Wang, and Xuding Zhu. Circular flows in mono-directed signed graphs.J. Graph Theory, 106(3):686–710, 2024

    2024

  11. [11]

    Kneser’s conjecture, chromatic number, and homotopy.J

    L´ aszl´ o Lov´ asz. Kneser’s conjecture, chromatic number, and homotopy.J. Comb. Theory, Ser. A, 25:319–324, 1978

    1978

  12. [12]

    Coloring Eulerian triangulations of the projective plane.Discrete Math., 244(1-3):339– 343, 2002

    Bojan Mohar. Coloring Eulerian triangulations of the projective plane.Discrete Math., 244(1-3):339– 343, 2002. 25

    2002

  13. [13]

    Bojan Mohar and Paul D. Seymour. Coloring locally bipartite graphs on surfaces.J. Comb. Theory, Ser. B, 84(2):301–310, 2002

    2002

  14. [14]

    Baltimore, MD: Johns Hopkins University Press, 2001

    Bojan Mohar and Carsten Thomassen.Graphs on surfaces. Baltimore, MD: Johns Hopkins University Press, 2001

    2001

  15. [15]

    Winding number and circular 4-coloring of (signed) graphs

    Reza Naserasr. Winding number and circular 4-coloring of (signed) graphs. 2022

    2022

  16. [16]

    Homomorphisms of signed graphs.J

    Reza Naserasr, Edita Rollov´ a, and ´Eric Sopena. Homomorphisms of signed graphs.J. Graph Theory, 79(3):178–212, 2015

    2015

  17. [17]

    Homomorphisms of signed graphs: an update

    Reza Naserasr, ´Eric Sopena, and Thomas Zaslavsky. Homomorphisms of signed graphs: an update. European J. Combin., 91:Paper No. 103222, 20, 2021

    2021

  18. [18]

    Circular chromatic number of signed graphs

    Reza Naserasr, Zhouningxin Wang, and Xuding Zhu. Circular chromatic number of signed graphs. Electron. J. Combin., 28(2):Paper No. 2.44, 40, 2021

    2021

  19. [19]

    Van Ngoc.On graph colorings (Hungarian)

    N. Van Ngoc.On graph colorings (Hungarian). Ph.D. Thesis, Hungarian Academy of Sciences, Bu- dapest. 1987

    1987

  20. [20]

    A. Nilli. Short odd cycles in 4-chromatic graphs.J. Graph Theory, 31(2):145–147, 1999

    1999

  21. [21]

    On the chromatic number of cube-like graphs.Discrete Math., 103(3):271–277, 1992

    Charles Payan. On the chromatic number of cube-like graphs.Discrete Math., 103(3):271–277, 1992

    1992

  22. [22]

    Michael Stiebitz.Beitr¨ age zur Theorie der f¨ arbungskritischen Graphen. 1985

    1985

  23. [23]

    Color-critical graphs on a fixed surface.J

    Carsten Thomassen. Color-critical graphs on a fixed surface.J. Comb. Theory, Ser. B, 70(1):67–100, 1997

    1997

  24. [24]

    4-chromatic graphs with large odd girth

    Nguyen Van Ngoc and Zsolt Tuza. 4-chromatic graphs with large odd girth. volume 138, pages 387–392

  25. [25]

    14th British Combinatorial Conference (Keele, 1993)

    1993

  26. [26]

    An Erdos-Gallai conjecture for signed graphs

    Lujia Wang. An Erdos-Gallai conjecture for signed graphs. Preprint, arXiv:2509.07724 [math.CO] (2025), 2025

    arXiv 2025

  27. [27]

    West.Introduction to graph theory

    Douglas B. West.Introduction to graph theory. Upper Saddle River, NJ: Prentice Hall, 1996

    1996

  28. [28]

    Dale A. Youngs. 4-chromatic projective graphs.J. Graph Theory, 21(2):219–227, 1996. 26

    1996