Pith. sign in

REVIEW 3 major objections 1 minor

Every planar graph has a 4-coloring in which no color is used on half or more of the vertices, and one can be found in O(n log n) time.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-15 01:28 UTC pith:63ZY6LMC

load-bearing objection Clean, tight algorithmic strengthening of 4CT claimed in the abstract; full proof and O(n log n) method are invisible, so this is still an unverified existence claim. the 3 major comments →

arxiv 2607.13025 v1 pith:63ZY6LMC submitted 2026-07-14 cs.DS math.CO

The Balanced Four-Color Theorem

Ken-ichi Kawarabayashi , Hirotaka Yoneda , Masataka Yoneda This is my paper
classification cs.DS math.CO MSC 05C1505C1068R10
keywords planar graphsfour color theorembalanced coloringequitable coloringsurface embeddingsgraph algorithms
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The classical Four Color Theorem guarantees that the vertices of any planar graph can be painted with four colors so that adjacent vertices receive different colors. This paper strengthens that guarantee by requiring the coloring also to be balanced: for a graph on n vertices (n at least 3), each of the four colors appears on strictly fewer than n/2 vertices. The authors prove that such a balanced 4-coloring always exists, that the bound cannot be improved in general, and that an explicit balanced coloring can be computed in O(n log n) time. They further show that the same style of balance statement holds when more than four colors are allowed and when the graph is embedded on an arbitrary surface rather than the plane. A reader who cares about equitable or load-balanced colorings therefore obtains both an existence theorem and a near-linear algorithm that enforce a simple, sharp size constraint on every color class.

Core claim

Every planar graph on n ≥ 3 vertices admits a proper 4-coloring in which each color class has size strictly less than n/2; the bound is tight, the coloring can be produced in O(n log n) time, and analogous balanced colorings exist for five or more colors and for graphs on general surfaces.

What carries the argument

A constructive O(n log n)-time procedure that produces a proper 4-coloring while maintaining the strict size bound |color class| < n/2 for every color; the same balance-preserving idea is then lifted to larger palettes and to surfaces of higher genus.

Load-bearing premise

That there exists a constructive algorithmic procedure, running in O(n log n) time, that produces a 4-coloring of every planar graph while keeping every color class strictly smaller than half the vertices.

What would settle it

Exhibit a planar graph on n ≥ 3 vertices that admits no proper 4-coloring in which every color appears fewer than n/2 times, or show that every algorithm producing such a balanced coloring requires ω(n log n) time on some infinite family of planar graphs.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 1 minor

Summary. The manuscript (available only as an abstract) claims that every planar graph on n ≥ 3 vertices admits a 4-coloring in which every color class has size strictly less than n/2, that this bound is tight, and that such a coloring can be computed in O(n log n) time. Parallel statements are asserted for five or more colors and for graphs embeddable on arbitrary surfaces.

Significance. If the claims hold, the result would strengthen the Four Color Theorem by imposing a strict global balance condition on color classes, together with a near-linear constructive algorithm. The tightness statement and the extensions to more colors and higher-genus surfaces would be of genuine interest in structural and algorithmic graph theory. The absence of free parameters and the explicit runtime bound are attractive features, provided they are supported by correct arguments.

major comments (3)
  1. [Abstract] The abstract asserts both existence of a strictly balanced 4-coloring and an O(n log n) algorithm that produces one, yet supplies neither a structural lemma, inductive reduction, nor algorithmic outline that would let a reader verify preservation of the strict < n/2 invariant. Ordinary 4-colorability does not automatically yield the balance condition; without these details the central claim cannot be assessed.
  2. [Abstract] Tightness of the < n/2 bound is declared but no extremal planar graph (or family) is exhibited showing that some color class must reach size floor(n/2). An elementary construction is needed to confirm that the inequality cannot be strengthened.
  3. [Abstract] The extensions to k ≥ 5 colors and to graphs on general surfaces are stated without any indication of how the balance invariant or the runtime analysis carries over. These claims inherit the same unverifiability as the planar 4-color case.
minor comments (1)
  1. The provided document consists solely of the abstract; no sections, proofs, figures, or references are present, so ordinary presentation issues cannot be evaluated.

Circularity Check

0 steps flagged

No circularity detectable: abstract-only claim against external planar graphs with no self-referential reduction exhibited.

full rationale

Only the abstract is available; it asserts that every planar graph on n≥3 vertices admits a 4-coloring with each color class of size strictly less than n/2 (tight) and that such a coloring can be produced in O(n log n) time, with extensions to more colors and surfaces. No equations, inductive steps, structural lemmas, fitted parameters, uniqueness theorems, or self-citations appear in the supplied text. The claim is therefore an existence-and-algorithm statement about the external class of planar graphs; nothing reduces the conclusion to a definitional identity or to a quantity fitted from the same data. Per the hard rules, an honest non-finding is required when no specific reduction can be quoted. Residual uncertainty about the unseen proof is a correctness/verifiability concern, not circularity. Score 0, steps empty.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

Abstract-only review: free parameters and invented entities are not introduced in the visible text. The claim rests on standard background of planar graph theory and the classical Four Color Theorem; any additional structural lemmas used in the unseen proof cannot be audited here.

axioms (3)
  • domain assumption Every planar graph is 4-colorable (Four Color Theorem).
    The balanced refinement presupposes ordinary 4-colorability of planar graphs; the abstract builds on this classical fact.
  • domain assumption Planarity (or embeddability on a surface) is the structural hypothesis under which the balance bound holds.
    The theorem is stated only for planar graphs and, in the extension, for graphs on general surfaces.
  • ad hoc to paper An O(n log n)-time constructive procedure exists that preserves the strict < n/2 balance invariant.
    Asserted in the abstract without proof or reduction; this is the paper-specific algorithmic claim.

pith-pipeline@v1.1.0-grok45 · 5950 in / 2039 out tokens · 27075 ms · 2026-07-15T01:28:10.218155+00:00 · methodology

0 comments
read the original abstract

We show that every planar graph with $n \geq 3$ vertices admits a 4-coloring in which each color is used on fewer than $n/2$ vertices. This bound is the best possible. Moreover, such a coloring can be found in $O(n \log n)$ time. We also extend these results to five or more colors and to graphs on general surfaces.

discussion (0)

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