Pith. sign in

REVIEW 2 major objections 5 minor 16 references

Planar graphs with girth at least 5 are (3,4)-colorable

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Every planar graph with girth at least 5 admits a (3,4)-coloring: its vertices split into two parts with internal maximum degrees 3 and 4.

desk verdict The (3,4)-coloring theorem is new and the discharging framework is substantial, but Lemma 2.2 has a load-bearing gap: recoloring the removed 3-vertex ignores the effect on its neighbors' color-class degrees. read the letter →

arxiv 1908.03172 v1 pith:YCIG6ZAY submitted 2019-08-08 math.CO

Ilkyoo Choi , Gexin Yu , Xia Zhang This is my paper · ORCID
classification math.CO MSC 05C1505C10
keywords impropercoloringdefective(34)-colorabilityplanargraphgirthatleast5dischargingmethodvertexpartitionmaximumdegree
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper establishes that planar graphs with no cycles of length 3 or 4 can be partitioned into two parts with bounded internal degree: one part has maximum degree at most 3 and the other at most 4. Equivalently, every such graph is $(3,4)$-colorable in the defective-coloring sense. This is the first known pair of allowed degrees summing to 7 for this class, improving the previous $(3,5)$ bound, and it narrows the open question of the best $(3,d)$ pair to three candidates: $d=2,3,4$. The significance is that a mild sparsity condition, namely girth at least 5, already forces a very uneven but still bounded two-way partition of the vertex set.

What carries the argument

The engine of the proof is a minimal-counterexample analysis combined with discharging. The central structural lemma (Lemma 2.3) asserts that in a minimal counterexample, deleting any vertex of degree at most 8 forces the existence of a saturated neighbor that cannot be recolored, with precise type guarantees (for example, a 4-saturated neighbor that is either a $9^+$-vertex or a $6^{s+}$-vertex). Saturated here means the neighbor already carries its full quota of same-colored neighbors. This lemma is used to rule out many face configurations. The discharging phase begins with initial charge $\mu(x)=d(x)-4$ on every vertex and face; Euler's formula makes the total charge $-8$, and the rules (R1), (R2), and (R3) redistribute charge so that each vertex and face ends nonnegative, a contradiction. Special named configurations such as poor, semi-poor, and rich vertices, heavy edges, and the face types $F_{5a},\dots,F_7$ carry the bookkeeping.

What would settle it

Exhibit a planar graph with girth at least 5 whose vertex set cannot be split into a part of maximum degree at most 3 and a part of maximum degree at most 4. The theorem asserts no such graph exists, so one example would refute it; a more local check would be to find, inside a supposed minimal counterexample, a vertex of degree at most 8 whose deletion leaves no non-recolorable saturated neighbor of the type promised by Lemma 2.3.

Watch

Extended reading notes

Core claim

The paper proves Theorem 1.2: every planar graph whose shortest cycle has length at least 5 admits a $(3,4)$-coloring, meaning its vertices can be split into two parts $A$ and $B$ such that each vertex of $A$ has at most 3 neighbors in $A$ and each vertex of $B$ has at most 4 neighbors in $B$. This is the first pair of allowed degrees with sum at most 7 known to work for all such graphs, improving the earlier $(3,5)$ result. The proof assumes a minimal counterexample and derives a rigid local structure: there are no 3-vertices, every edge is incident with a vertex of degree at least 5, and faces can carry only limited combinations of low-degree and poor vertices. A discharging argument then assigns initial charge $d(x)-4$ to every vertex and face, moves charge by explicit rules, and shows every element ends with nonnegative charge, contradicting Euler's formula, which fixes the total charge at $-8$.

Load-bearing premise

The proof depends on the assertion that in a smallest counterexample, deleting a vertex of degree at most 8 always leaves a neighbor that already has its full quota of same-colored neighbors and cannot be recolored, with exactly the degree and type guarantees the later lemmas use; if that recoloring analysis is wrong anywhere, the discharging argument loses its foundation.

Editorial extensions

If this is right

  • Every planar graph with girth at least 5 now has a vertex partition into a part of maximum degree at most 3 and a part of maximum degree at most 4, improving the previous $(3,5)$-colorability bound.
  • Because a known construction shows girth-5 planar graphs need not be $(3,1)$-colorable, the optimal second parameter in the $(3,d)$ question is now known to lie in $\{2,3,4\}$.
  • Since the result holds for every planar graph with girth at least 5, it automatically covers all planar graphs with larger girth, including triangle-free and 4-cycle-free families.
  • The discharging bookkeeping isolates the finite family of local configurations that any minimal counterexample would have to contain; if the theorem is right, none of those configurations can actually occur.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, the same discharging scheme might be adapted to attack $(3,3)$- or even $(3,2)$-colorability by strengthening Lemma 2.3 for low-degree vertices; the paper does not claim such a strengthening.
  • Beyond the paper, because planarity enters only through Euler's formula and face lengths, an analogous discharging proof may extend to graphs on surfaces with sufficiently large girth, though the charge targets would change.
  • Beyond the paper, a computer search over all planar graphs of girth 5 up to moderate order for $(3,4)$-, $(3,3)$-, and $(3,2)$-colorings could test how close these bounds are to sharp and would give a concrete target for a counterexample if one exists.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper proves that every planar graph with girth at least 5 admits a vertex partition into two sets inducing subgraphs of maximum degree at most 3 and 4, respectively. The proof uses a minimal counterexample, structural lemmas on forbidden configurations, and a discharging argument. This would be the first (d1,d2)-coloring result with d1+d2≤7 for planar graphs of girth 5.

Significance. If correct, Theorem 1.2 is a genuine improvement over the previous best (3,5)-coloring and narrows the answer to Question 1.3 to d_2∈{2,3,4}. The paper is self-contained and follows the standard discharging paradigm. However, the current proof has a serious gap in Lemma 2.2 that affects the discharging analysis.

major comments (2)
  1. [Lemma 2.2] The final step of the proof is not justified. After fixing φ(u1)=φ(u2)=c, the authors assert that coloring v with c gives a (3,4)-coloring of G because each vi has a neighbor in {u1,u2}. This only ensures that v itself has at most 3 same-colored neighbors. It does not check whether a neighbor vi that is already colored c in H would exceed its allowed c-degree when v is added. If vi already has c same-colored neighbors in H, then after adding v its c-degree becomes c+1, violating the definition. No bound on the c-degree of the vi's in H nor any recoloring of the vi's is given. Since Lemma 2.2 is the only argument excluding 3-vertices, and the discharging rules (R1)-(R3) give nothing to 3-vertices, Lemma 3.5's assertion d(u)≠3 is unsupported. The proof of Theorem 1.2 is therefore incomplete.
  2. [Lemma 2.3] In the proof, after selecting a non-recolorable j-saturated neighbor u of v, the claim 'if d(u)≤8, then x must be i-saturated' is not generally true. A recoloring of u with i can be impossible because u itself would acquire i+1 i-colored neighbors, even if no i-colored neighbor of u is saturated. For example, if u has exactly i i-colored neighbors, then d(u)=1+j+i=8, consistent with d(u)≤8. The structural conclusions (i)-(iii) rely on this assertion and are used throughout the case analyses in Lemmas 2.4-2.7 and 3.2-3.4; the argument needs to handle the alternative that u has i i-colored neighbors.
minor comments (5)
  1. [Title] The title contains a typo: 'GIR TH' should be 'GIRTH'.
  2. [Section 1, Question 1.3] The notation 'd3 2' is garbled; it should be typeset as d_2^3 or described in words.
  3. [Lemma 3.1] The expression 'µ∗(f)≥ 7−4−max{...}' is confusing because 7−4 is the initial charge; consider writing 3−max{...}.
  4. [Section 3, rules (R3d)] The phrase 'distributes its charge evenly to each incident 5p-, 5s-, and 6p-vertex (if any exist)' is ambiguous when the face has two 2-vertices; please clarify whether the equal split includes the 2-vertices.
  5. [References] The arXiv preprint [8] is cited as 'ArXiv e-prints, March 2016'; please update with the journal reference if available.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is a self-contained minimal-counterexample and discharging argument.

full rationale

The paper proves Theorem 1.2 by assuming a minimal counterexample G, deriving structural restrictions on G through Lemmas 2.1–2.7, and then reaching a contradiction via the discharging rules in Section 3. No step assumes the target theorem, and no step fits a parameter to the data it later claims to predict. Lemma 2.3, the key structural tool, is proved internally from the existence of a (3,4)-coloring of G−v: it uses the definition of saturation and the fact that v cannot be colored to infer structural properties of neighbors. This is a standard minimal-counterexample argument, not a circular one. The cited prior results (e.g., (3,5)-colorability in [9], (2,6)-colorability in [6], (4,4)-colorability in [16]) are used only to position the result in the literature, not as load-bearing premises of the derivation. Even if Lemma 2.2 or parts of Lemma 2.4 contain a gap or an unverified recoloring detail, that would be a correctness concern, not a circularity concern: the argument does not smuggle in its conclusion through definitions, fitted inputs, or author-imported uniqueness theorems. The discharging rules are justified by the structural lemmas and the charge-counting inequality, and the final contradiction is obtained from Euler’s formula. The paper is therefore self-contained against its own assumptions and does not reduce to its inputs by construction.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The proof is a pure mathematical derivation. No empirical parameters are fitted; the only 'chosen' constants are discharging weights, which are proof design choices. No new entities are postulated.

free parameters (2)
  • discharging transfer weight for 2-vertices = 1/2
    Chosen in R1 and R3 so that every 2-vertex ends with zero charge; a proof design choice rather than an empirical fit.
  • discharging transfer weights for special faces (F6a, F6b, F7, F5a-F5d) = 3/8, 1/4, 1/6, 1/8
    These weights in R3 prevent negative final charge on special faces; they are chosen ad hoc to satisfy the inequalities in Lemma 3.1.
assumptions (3)
  • standard math Euler's formula sum_{v,f}(d(v)-4) = -8 for connected planar graphs
    Initial charge definition and the contradiction rely on Euler's formula.
  • standard math Every graph has a counterexample with minimum number of 3+-vertices if any counterexample exists
    Minimal counterexample selection is well-founded.
  • domain assumption The graph is finite, simple, planar, and every face has length at least 5 (girth condition)
    These are the conditions of Theorem 1.2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Planar graphs with girth at least 5 are (3,4)-colorable." pith.science (2026). https://pith.science/paper/YCIG6ZAY

@misc{pith2026190803172,
  author       = {Pith},
  title        = {Pith review of: Planar graphs with girth at least 5 are (3,4)-colorable},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YCIG6ZAY}},
  note         = {Machine review of arXiv:1908.03172}
}
abstract

A graph is $(d_1, \ldots, d_k)$-colorable if its vertex set can be partitioned into $k$ nonempty subsets so that the subgraph induced by the $i$th part has maximum degree at most $d_i$ for each $i\in\{1, \ldots, k\}$. It is known that for each pair $(d_1, d_2)$, there exists a planar graph with girth $4$ that is not $(d_1, d_2)$-colorable. This sparked the interest in finding the pairs $(d_1, d_2)$ such that planar graphs with girth at least $5$ are $(d_1, d_2)$-colorable. Given $d_1\leq d_2$, it is known that planar graphs with girth at least $5$ are $(d_1, d_2)$-colorable if either $d_1\geq 2$ and $d_1+d_2\geq 8$ or $d_1=1$ and $d_2\geq 10$. We improve an aforementioned result by providing the first pair $(d_1, d_2)$ in the literature satisfying $d_1+d_2\leq 7$ where planar graphs with girth at least $5$ are $(d_1, d_2)$-colorable. Namely, we prove that planar graphs with girth at least $5$ are $(3, 4)$-colorable.

Figures

Figures reproduced from arXiv: 1908.03172 by the authors.

Figure 1
Figure 1. Obtaining H from G in Lemma 2.2. Without loss of generality, we may assume ϕ(u1) = ϕ(u2). Since each of v1, v2, v3 has a neighbor in {u1, u2}, using the color ϕ(u1) on v gives a (3, 4)-coloring of G, which is a contradiction. Lemma 2.3. If v is an 8 −-vertex of G, then in every (3, 4)-coloring of G − v, v has a saturated neighbor in G − v that cannot be recolored. In particular, (i) if d(v) = 2, then for each i ∈ {3… view at source ↗
Figure 2
Figure 2. Special 7-face, 6-faces, and 5-faces Here are the discharging rules: (R1) Let v be a 5+-vertex. Then v gives 1 2 to each adjacent 2-vertex; moreover, 7 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. A 5p-vertex u incident with five 5+-faces and a 6p-vertex u incident with six 5+-faces. To get some idea regarding the degrees of the vertices on the five faces incident with u, we consider a (3, 4)-coloring ϕ of G − u, which exists since the number of edges decreased and the number of 3+-vertices did not increase. By Lemma 2.3 (ii), u0 is a 4-saturated 6+-vertex and the four 2-neighbors of u are colored with the co… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Two possible embeddings containing 5s-vertex u with five 5-faces. 13 [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Appel and W

    K. Appel and W. Haken. Every planar map is four colorable. I. Discharging. Illinois J. Math., 21(3):429-490, 1977

    work page 1977

  2. [2]

    Appel, W

    K. Appel, W. Haken, and J. Koch. Every planar map is four colorable. II. Reducibility. Illinois J. Math., 21(3):491-567, 1977

    work page 1977

  3. [3]

    O. V. Borodin, A. O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k. J. Graph Theory, 65(2):83-93, 2010

    work page 2010

  4. [4]

    O. V. Borodin, A. Kostochka, and M. Yancey. On 1-improper 2-coloring of sparse graphs. Discrete Math., 313(22):2638-2649, 2013

    work page 2013

  5. [5]

    O. V. Borodin and A. V. Kostochka. Vertex decompositions of sparse graphs into an independent set and a subgraph of maximum degree at most 1. Sibirsk. Mat. Zh., 52(5):1004-1010, 2011

    work page 2011

  6. [6]

    O. V. Borodin and A. V. Kostochka. Defective 2-colorings of sparse graphs. J. Combin. Theory Ser. B, 104:72-80, 2014

    work page 2014

  7. [7]

    (1 , k)-coloring of graphs with girth at least five on a surface

    Hojin Choi, Ilkyoo Choi, Jisu Jeong, and Geewon Suh. (1 , k)-coloring of graphs with girth at least five on a surface. J. Graph Theory, 84(4):521-535, 2017

    work page 2017

  8. [8]

    Choi and L

    I. Choi and L. Esperet. Improper coloring of graphs on surfaces. ArXiv e-prints, March 2016

    work page 2016

Show all 16 references
  1. [9]

    Planar graphs with girth at least 5 are (3 , 5)-colorable

    Ilkyoo Choi and Andr´ e Raspaud. Planar graphs with girth at least 5 are (3 , 5)-colorable. Discrete Math., 338(4):661-667, 2015

    2015

  2. [10]

    L. J. Cowen, R. H. Cowen, and D. R.Woodall. Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency. J. Graph Theory, 10(2):187-195, 1986

    1986

  3. [11]

    Defective list colorings of planar graphs

    Nancy Eaton and Thomas Hull. Defective list colorings of planar graphs. Bull. Inst. Combin. Appl., 25:79-87, 1999

    1999

  4. [12]

    Zur Theorie der diskreten Gebilde

    Herbert Gr¨ otzsch. Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz f¨ ur dreikreisfreie Netze auf der Kugel. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe, 8:109-120, 1958/1959

    1958

  5. [13]

    Improper choosability of graphs and maximum average degree

    Fr´ ed´ eric Havet and Jean-S´ ebastien Sereni. Improper choosability of graphs and maximum average degree. J. Graph Theory, 52(3):181-199, 2006

    2006

  6. [14]

    Montassier and P

    M. Montassier and P. Ochem. Near-colorings: non-colorable graphs and NP-completeness. Electron. J. Combin., 22(1):Paper 1.57, 13, 2015

    2015

  7. [15]

    ˇSkrekovski

    R. ˇSkrekovski. List improper colourings of planar graphs. Combin. Probab. Comput., 8(3):293-299, 1999

    1999

  8. [16]

    List improper colorings of planar graphs with prescribed girth

    Riste ˇSkrekovski. List improper colorings of planar graphs with prescribed girth. Discrete Math., 214(1-3):221- 233, 2000. 1 Department of Mathematics, Hankuk University of Foreign Studies, Yongin-si, Gyeonggi-do, Re- public of Korea, ilkyoo@hufs.ac.kr. 2Department of Mathema...

    2000

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.