arxiv: 2604.22705 · v1 · submitted 2026-04-24 · 🧮 math.CO · math.GR

Recognition: unknown

Planar 1-ended graphs can be periodically coloured

Luke Waite

Authors on Pith no claims yet

Pith reviewed 2026-05-08 10:59 UTC · model grok-4.3

classification 🧮 math.CO math.GR

keywords periodic colouringplanar graphsone-ended graphsvertex colouringisometry groupsEuclidean graphshyperbolic planelocally finite graphs

0 comments

The pith

Planar graphs with one end always permit periodic proper vertex colourings.

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

The paper establishes that every planar graph with exactly one end admits a periodic proper vertex colouring. A colouring is periodic when the coloured graph has only finitely many orbits under its colour-preserving automorphisms. The argument proceeds by constructing embeddings of the graph into the Euclidean or hyperbolic plane that respect isometries, then applying known orbit properties of those isometry groups. For the Euclidean case the construction yields a proper colouring with five colours. This result concludes an investigation into periodic colourings of locally finite graphs by showing that planarity plus one end is sufficient for the property.

Core claim

We prove that every planar graph with one end admits a periodic proper vertex colouring. This is shown by constructing isometry-respecting embedded maps into the Euclidean and hyperbolic planes and leveraging known properties of their isometry groups. Moreover, when the graph is Euclidean this colouring can always be done using five colours.

What carries the argument

isometry-respecting embedded maps of the graph into the Euclidean or hyperbolic plane, whose isometry groups act with finitely many orbits on the coloured vertices

If this is right

Every planar graph with one end has a periodic proper vertex colouring.
Every Euclidean planar graph with one end has a periodic proper vertex colouring that uses at most five colours.
The resulting coloured graph has only finitely many orbits under its colour-preserving automorphism group.
The same conclusion holds for all locally finite graphs that are planar and one-ended.

Where Pith is reading between the lines

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

The same embedding technique may extend to other infinite graphs embeddable in spaces whose isometry groups have finite-orbit actions.
Periodic colourings reduce the study of symmetries on certain infinite planar graphs to the study of finite quotients.
The result supplies a concrete construction for periodic colourings of graphs that arise as skeletons of tilings in the plane or hyperbolic plane.
It remains open whether five colours suffice for all planar one-ended graphs or only the Euclidean ones.

Load-bearing premise

Every planar one-ended graph admits an embedding into the Euclidean or hyperbolic plane that respects isometries and whose isometry group has the required orbit properties on the vertices.

What would settle it

Exhibit a specific planar graph with exactly one end that has no periodic proper vertex colouring, or show that for some such graph no isometry-respecting embedding into the Euclidean or hyperbolic plane exists with the necessary orbit properties.

Figures

Figures reproduced from arXiv: 2604.22705 by Luke Waite.

**Figure 1.** Figure 1: A 2-colouring of the Cayley graph of Z × Z that is (2Z × 2Z)-periodic. Of these highly symmetric graphs, those that are planar are of particular interest as they naturally arise as periodic tilings of the planar geometries. As such they induce embeddings of their finite quotients onto welldefined quotient surfaces. In this paper we prove the answer to Problem 1.2 in the negative. That is: Theorem 1.1. Let… view at source ↗

**Figure 2.** Figure 2: F contains a second disjoint maximal halfspace H′ F view at source ↗

**Figure 4.** Figure 4: HF is unique and there is at least one side S not incident with ℓF view at source ↗

read the original abstract

We conclude an investigation of Abrishami, Esperet, Giocanti, Hamman, Knappe and M\"oller studying the existence of periodic colourings of locally finite graphs. A colouring of a graph $\Gamma$ is periodic if the resulting coloured graph has a finite number of orbits under its colour-preserving automorphisms, as such it is natural to consider those quasi-transitive graphs with finite quotient. In the case that the graph is planar and has 1-end we prove that it always permits a periodic proper vertex colouring. This is shown by constructing isometry respecting embedded maps into the Euclidean and hyperbolic planes and leveraging known properties of Euclidean and hyperbolic isometry groups. Moreover, in the case that a graph is Euclidean we show that this can always be done in 5 colours.

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.

Desk Editor's Note private letter to a colleague

The paper proves every planar 1-ended graph has a periodic proper vertex coloring via isometry-respecting embeddings into Euclidean or hyperbolic planes, with a 5-color bound when the graph is Euclidean.

read the letter

Every planar 1-ended graph admits a periodic proper vertex coloring, and the Euclidean ones can be done with five colors. The authors reach this by building embeddings into the Euclidean or hyperbolic plane that respect isometries and then using the orbit properties of those groups to get finitely many orbits on the colored vertices. This completes the study from Abrishami, Esperet, Giocanti, Hamman, Knappe and Möller. The new construction via plane embeddings handles the 1-ended planar case, and the 5-color bound for Euclidean graphs is fresh. The paper does well by sticking to known facts about isometry groups rather than new combinatorial arguments. The main concern is whether those embeddings exist and work uniformly for every planar 1-ended graph. The argument requires that the image has color-preserving isometries with only finitely many orbits on the vertices. If some graphs resist this kind of rigid embedding, the guarantee does not hold. I would look closely at the construction to see if it is general or if there are hidden assumptions. This paper is for specialists in infinite graph theory and geometric colorings. A reader following work on quasi-transitive graphs will get value from the explicit result. It deserves a serious referee because it provides a concrete existence proof that closes a cited gap. I recommend putting it through peer review. The idea is sound and the approach is economical, though the embedding details will need verification.

Referee Report

0 major / 3 minor

Summary. The manuscript proves that every planar 1-ended locally finite graph admits a periodic proper vertex colouring. The argument proceeds by constructing, for any such graph, an isometry-respecting embedding into the Euclidean or hyperbolic plane so that the image admits a proper vertex colouring whose colour-preserving isometries have only finitely many orbits on the vertex set; periodicity then follows from the known orbit structure of the isometry groups. In the Euclidean case the construction yields a 5-colouring.

Significance. This completes the programme initiated by Abrishami, Esperet, Giocanti, Hamman, Knappe and Möller on periodic colourings of locally finite graphs, at least for the planar 1-ended case. The reduction to standard facts about Euclidean and hyperbolic isometry groups (finite orbits on vertices after colouring) is a genuine strength, as is the explicit geometric construction that avoids ad-hoc parameter fitting. If the embedding step is uniform and works for every planar 1-ended graph, the result supplies a clean existence theorem with a concrete bound in the Euclidean setting.

minor comments (3)

Abstract, final sentence: the phrase 'in the case that a graph is Euclidean' is ambiguous; it should be clarified whether this means the graph admits a Euclidean embedding, is quasi-isometric to the plane, or satisfies some other geometric condition used in the construction.
The manuscript should include a short paragraph in the introduction explicitly comparing the new embedding technique with the methods of Abrishami et al., so that readers can see precisely which step is novel.
Notation for the isometry groups and their actions on coloured vertices should be introduced once in a preliminary section and used consistently thereafter to avoid repeated re-definition.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the supportive summary, the recognition that the work completes the programme on periodic colourings for the planar 1-ended case, and the recommendation of minor revision. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No circularity: explicit construction plus external group properties

full rationale

The paper claims to prove the existence of periodic proper vertex colourings for planar 1-ended graphs by explicitly constructing isometry-respecting embeddings into the Euclidean or hyperbolic plane and then applying known orbit properties of the corresponding isometry groups. No equations are shown to be self-definitional, no fitted parameters are relabelled as predictions, and no load-bearing step reduces to a self-citation whose content is itself unverified. The isometry-group facts are standard external results, not derived inside the paper. Because the central step is a claimed construction rather than a renaming or tautological re-expression of the input, the derivation chain remains independent of the target statement.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof rests on the existence of distance-preserving embeddings of the graph into the Euclidean or hyperbolic plane together with standard facts about their isometry groups; no free parameters or invented entities are introduced in the abstract.

axioms (2)

domain assumption Planar 1-ended graphs admit isometry-respecting embeddings into Euclidean or hyperbolic plane
Invoked in the construction step of the abstract
standard math Isometry groups of Euclidean and hyperbolic planes have finite-orbit properties usable for coloring
Leveraged to obtain periodic coloring

pith-pipeline@v0.9.0 · 5420 in / 1254 out tokens · 24305 ms · 2026-05-08T10:59:14.859812+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

2 extracted references

[1]

M¨ oller

[AEG+25] Tara Abrishami, Louis Esperet, Ugo Giocanti, Matthias Hamann, Paul Knappe, and R¨ ognvaldur G. M¨ oller. Periodic colorings and orientations in infinite graphs, 2025.https://arxiv.org/abs/2411. 01951. 1, 2, 13 [And05] J. Anderson.Hyperbolic Geometry. Springer Undergraduate Mathematics Series. Springer London,

2025
[2]

Sedl´ aˇ cek

6, 14 [Sed64] J. Sedl´ aˇ cek. Some properties of interchange graphs. InTheory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pages 145–150. Publ. House Czech. Acad. Sci., Prague,

1963