Pith. sign in

REVIEW 3 major objections 5 minor 22 references

Planar graphs without normally adjacent short cycles

T0 review · 3 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 plane graph in the class $\mathscr{G}$ — with no triangle normally adjacent to an $8^{-}$-cycle, no $4$-cycle normally adjacent to a $6^{-}$-cycle, and no normally adjacent $5$-cycles — is $3$-choosable, proved through a stronger…

desk verdict Genuine extension of the known 3-choosability results, but the pivotal Lemma 2.8 is under-verified and the IF-coloring section is a sketch. read the letter →

arxiv 1908.04902 v4 pith:BSZCKAAX submitted 2019-08-14 math.CO cs.DM

Fangyao Lu , Mengjiao Rao , Qianqian Wang , Tao Wang This is my paper · ORCID
classification math.COcs.DM MSC 05C1505C10
keywords planargraph3-choosabilitylistcoloringDP-coloringnormallyadjacentcyclesdischargingmethodIF-coloringnear-bipartite
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 proves that every plane graph in the class $\mathscr{G}$ — no triangle normally adjacent to an $8^{-}$-cycle, no $4$-cycle normally adjacent to a $6^{-}$-cycle, and no normally adjacent $5$-cycles — admits a proper list coloring from lists of size $3$. The proof establishes a stronger 'weakly DP' statement: any consistent $3$-matching-assignment coloring of a set $S$ of at most $12$ vertices, where $S$ is a single vertex or the vertices of a normal cycle, extends to the whole graph. Two cycles are normally adjacent when they share exactly one edge, and a normal cycle is any cycle that is not one of the two exceptional 11- or 12-cycles. This extension theorem implies the $3$-choosability of the whole class, and as corollaries it settles two previously open list-coloring cases: planar graphs without $4$-, $6$-, $8$-cycles and planar graphs without $4$-, $5$-, $7$-, $8$-cycles are both $3$-choosable. A companion theorem shows every graph in $\mathscr{G}$ also admits an IF-coloring, a partition of the vertices into an independent set and a set inducing a forest.

What carries the argument

The load-bearing mechanism is the minimal-counterexample reduction combined with discharging. Structural lemmas, especially Lemma 2.8, show that identifying a vertex $u_1$ with a vertex $v_3$ of an internal face keeps the reduced graph inside $\mathscr{G}$, which lets a precoloring of the smaller graph extend back to the original vertices. The discharging rules assign initial charges $\deg(v)-4$ to vertices and $\deg(f)-4$ to faces, redistribute them along incidences, and force every element to nonnegative final charge with at least one positive, contradicting the standard charge-sum identity for plane graphs. Two supporting tools are essential: a renaming lemma that makes the edges of a consistently covered subgraph straight, and a cover-coloring result stating that a cycle with a 2-list cover that is neither of the two exceptional ladder covers admits a coloring, used to rule out internal faces whose vertices all have degree three.

What would settle it

Look for a graph in $\mathscr{G}$ containing an internal 4- or 5-face whose every vertex has degree 3, glue together the two vertices $u_1$ and $v_3$ as Lemma 2.8 does, and check whether a new cycle of length at most 8 becomes normally adjacent to a 3-cycle; such a graph would be a direct counterexample to Lemma 2.9. A small exhaustive search over plane graphs in $\mathscr{G}$ with such a face would settle the claim.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.7: every graph in $\mathscr{G}$ is $3$-choosable, where $\mathscr{G}$ is the class of plane graphs without triangles normally adjacent to $8^{-}$-cycles, without $4$-cycles normally adjacent to $6^{-}$-cycles, and without normally adjacent $5$-cycles. To obtain it, the authors prove Theorem 1.6, a weak DP-coloring extension result: if $S$ has at most $12$ vertices and is either a single vertex or a normal cycle, then every consistent $3$-matching-assignment coloring of $G[S]$ extends to an $M$-coloring of $G$. Here $M$-coloring means a proper coloring of the DP cover, and the consistency condition is imposed only on closed walks of length three. The proof runs by minimal counterexample, structural lemmas showing that every $8^{-}$-cycle has no chords and that certain internally degree-three faces cannot occur, and a discharging argument that redistributes charges until a contradiction is reached. The same machinery yields Theorem 1.15: every graph in $\mathscr{G}$ has an IF-coloring, i.e., its vertex set partitions into an independent set and a set inducing a forest.

Load-bearing premise

Everything rests on Lemma 2.8's claim that when the two vertices $u_1$ and $v_3$ are glued together, no new forbidden short cycle is created; if that case analysis misses a path, the reduced graph falls outside $\mathscr{G}$ and the induction cannot proceed.

Editorial extensions

If this is right

  • Every planar graph without $4$-, $6$-, $8$-cycles is $3$-choosable.
  • Every planar graph without $4$-, $5$-, $7$-, $8$-cycles is $3$-choosable.
  • Every graph in $\mathscr{G}$ is IF-colorable: its vertices can be partitioned into an independent set and a set inducing a forest.
  • The main theorem improves the earlier $3$-choosability result for planar graphs without adjacent cycles of length at most $8$, allowing adjacent cycles of length $6$ to $8$ and replacing face precolorings by precolorings of normal cycles.

Reading between the lines

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

  • The same discharging architecture may transfer to neighboring forbidden-cycle classes: relaxing the adjacency condition on $5$-cycles would make the theorem imply DP-$3$-colorability of planar graphs without $3$-, $6$-, $7$-cycles, an open problem the paper names explicitly.
  • The existence of exceptional abnormal 11- and 12-cycles shows the precoloring-extension statement is genuinely tight; a natural testable extension is to classify all minimal obstructions to extension when the cycle is abnormal.
  • Because the IF-coloring theorem comes from the same structural lemmas, the near-bipartite conclusion is likely not an isolated fact: one could probe whether nearby classes, such as graphs without $3$-, $7$-, $8$-cycles, also admit IF-colorings, another open problem listed in the paper.
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

3 major / 5 minor

Summary. The paper studies plane graphs in the class G, defined by forbidding triangles normally adjacent to 8^-cycles, 4-cycles normally adjacent to 6^-cycles, and normally adjacent 5-cycles. The main result, Theorem 1.6, is a 'weakly' DP-3-coloring statement: if S has size at most 12 and is either a single vertex or the vertex set of a normal cycle, then any precoloring of G[S] that is consistent on closed walks of length three extends to an M-coloring of G. This yields Theorem 1.7, that every graph in G is 3-choosable, and the corollaries that planar graphs without 4-,6-,8-cycles and without 4-,5-,7-,8-cycles are 3-choosable. Section 3 states an analogous superextension theorem for IF-colorings, giving a near-bipartite partition result, and Section 4 discusses tightness and open problems. The proof of Theorem 1.6 follows the standard minimal-counterexample and discharging framework, with structural lemmas on short faces and a vertex-identification reduction in Lemma 2.8.

Significance. If the proofs are completed, the results are significant. Theorem 1.7 generalizes the 3-choosability theorems of Dvořák-Postle and Liu-Li, and Corollaries 1.8 and 1.9 give clean new sufficient conditions. The IF-coloring result extends a recent result of Liu and Yu. The overall strategy is sound in outline: the paper extends external benchmarks rather than fitting parameters to a target conclusion, and the discharging rules R1-R8 are explicit and checkable. The paper also honestly discusses the limitations of the method in Remark 2 and Section 4. No circularity was found in the main argument; the only self-citation, Theorem 1.16, is used as a tool rather than as the target claim. The main concerns are completeness of key structural proofs, not the architecture of the proof.

major comments (3)
  1. [§2, Lemma 2.8] The proof that G* belongs to G is the load-bearing step of the reduction, but it is not written in sufficient detail. The two cases are concluded by 'It is easy to check' and 'It is observed' assertions that are not derived: in case (i) the claim that |E(P)|≤8 forces |E(P)|=8 and Q to be a separating abnormal 11-cycle, and in case (ii) the equality characterizations |Q1|=|Q2|=6 for |E(P)|=7 and |Qi|=6, |Q3-i|=7 for |E(P)|=8. These claims are exactly what rule out new short cycles after identifying u1 and v3. In addition, the sentence 'there are no 3-cycles normally adjacent to abnormal cycles' is used as if it were part of the definition of G; it must be derived from the unproved Observation on abnormal cycles. The preservation of the other two forbidden adjacency conditions under the identification should also be stated explicitly rather than left to the phrase 'satisfies the requirement for adjacency in Theorem 1.6'. Since Lemma 2.9 removes internal (3,3,3,3)- and (3,3,3,3,3)-faces using exactly this reduction, and the discharging rules depend on that removal, a complete proof of Lemma 2.8 is required before the main theorem can be accepted.
  2. [§3, Theorem 3.1] Theorem 3.1 is announced and then only a 'Sketch of a proof' is provided. The reader is told that the structural lemmas are the same and that 'the discharging part is the same with that in Theorem 3.1', and Lemma 3.2 is placed in an appendix with the note that it 'will be deleted in the published version'. As a consequence, the IF-coloring theorem, which is highlighted in the abstract and yields Theorem 3.2, is not actually proved in the manuscript. Please provide a complete proof or a precise reduction to Section 2 that specifies how the IF-coloring superextension property is handled in each structural lemma and in the discharging phase.
  3. [§1, Observation] The Observation following Theorem 1.6 (every edge on an abnormal 12^-cycle is contained in a 4-, 5-, 6- or 7-cycle, and every vertex not on a normal 12^-cycle O has at most two neighbors on O) is used in Lemma 2.2(g), Lemma 2.8, and in the face-charge analysis, but no proof is given. Since the abnormal cycles are the finite list in Fig. 1, a short explicit verification should be included; currently this is an unproved load-bearing assertion.
minor comments (5)
  1. [Abstract] The phrase 'it is showed' should be 'it is shown'.
  2. [§3, Lemma 3.3] The proof of Lemma 3.3 refers to 'Lemma 2.1', but Lemma 2.1 states that every 8^-cycle has no chords; the intended reference appears to be Lemma 2.3.
  3. [§2, Lemma 2.4] In the last paragraph of the proof, the statement 'By the adjacency of cycles, x2x3 is only contained in a unique triangle' should be justified briefly: because two triangles sharing an edge would be normally adjacent, and G has no triangles normally adjacent to 8^-cycles.
  4. [§2, Lemma 2.2(f)] In the step where a chord w1w2 is added to form G', the text says 'We can easily check that G' is a plane graph satisfying the assumption of Theorem 1.6'; please spell out why the new graph remains in G and why the matching assignment remains consistent on closed walks of length three.
  5. [Appendix] The sentence in the appendix that the proof of Lemma 3.2 'will be deleted in the published version' should be removed; the submitted manuscript should be self-contained.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular reductions found; the proof is a self-contained minimal-counterexample/discharging argument, with only a non-load-bearing self-citation.

full rationale

I walked the derivation chain from the definition of G through the structural lemmas to the discharging rules. The main theorem (1.6/1.7) is not defined in terms of its conclusion: G is an independent structural class, and the 'normal cycle' restriction is justified by separately observed non-extendable configurations, not by assuming the desired extension. The minimal-counterexample reductions (Lemmas 2.2, 2.5, 2.8, 2.9) use the theorem only for strictly smaller graphs after checking that the smaller graphs belong to the same class, which is standard induction rather than circularity. The discharging rules are not fitted to data; they define an initial charge satisfying Euler's formula and redistribute it to force a contradiction, a proof technique rather than a prediction. The only self-citation is Theorem 1.16, credited to both the external reference [8] (Kim–Ozeki) and the authors' preprint [16], and it is used as a tool in Lemma 2.9 to color a 2-list cycle cover; it is not the target claim and is independently grounded, so it does not make the derivation circular. The appendix note that Lemma 3.2's proof 'will be deleted in the published version' and the cross-references for Lemmas 3.3/3.7 are omitted-proof/completeness issues in the IF-coloring section, not circular steps. The skeptic's concern about Lemma 2.8 under-checking some forbidden adjacencies is a possible correctness gap, but it is not a case of a conclusion being assumed as an input; it would make the proof incomplete, not circular.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters or invented entities; graph coloring proofs do not fit numerical data. The central claim relies on two external theorems (Dvorak-Postle equivalence and the cover-coloring theorem), Euler's formula, and an unproved observation about normal cycles used in the structural lemmas.

assumptions (4)
  • domain assumption Dvorak-Postle Theorem 1.1: a graph is k-choosable iff it is M-colorable for every consistent k-matching assignment.
    Bridges DP-coloring and list-coloring; used to conclude 3-choosability from the weak DP-coloring statement of Theorem 1.6.
  • domain assumption Theorem 1.16: a cycle cover with a 2-list assignment has an M-coloring unless it is a circular or Mobius ladder.
    External result derived from Kim-Ozeki [8] and the authors' own preprint [16]; used in Lemma 2.9 to rule out the last obstacle when extending the cover coloring.
  • standard math Euler's formula and the initial charge sum equation (3).
    Basis for the discharging method; the sum of initial charges is zero.
  • domain assumption Observation: Every 10−-cycle is normal, and every vertex outside a normal 12−-cycle has at most two neighbors on it.
    Stated without proof; used in Lemma 2.2(g) and in the 7-face discharging case to identify abnormal outer cycles.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Planar graphs without normally adjacent short cycles." pith.science (2026). https://pith.science/paper/BSZCKAAX

@misc{pith2026190804902,
  author       = {Pith},
  title        = {Pith review of: Planar graphs without normally adjacent short cycles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BSZCKAAX}},
  note         = {Machine review of arXiv:1908.04902}
}
abstract

Let $\mathscr{G}$ be the class of plane graphs without triangles normally adjacent to $8^{-}$-cycles, without $4$-cycles normally adjacent to $6^{-}$-cycles, and without normally adjacent $5$-cycles. In this paper, it is shown that every graph in $\mathscr{G}$ is $3$-choosable. Instead of proving this result, we directly prove a stronger result in the form of ``weakly'' DP-$3$-coloring. The main theorem improves the results in [J. Combin. Theory Ser. B 129 (2018) 38--54; European J. Combin. 82 (2019) 102995]. Consequently, every planar graph without $4$-, $6$-, $8$-cycles is $3$-choosable, and every planar graph without $4$-, $5$-, $7$-, $8$-cycles is $3$-choosable. In the third section, using almost the same technique, we prove that the vertex set of every graph in $\mathscr{G}$ can be partitioned into an independent set and a set that induces a forest, which strengthens the result in [Discrete Appl. Math. 284 (2020) 626--630]. In the final section, tightness is discussed.

Figures

Figures reproduced from arXiv: 1908.04902 by the authors.

Figure 1
Figure 1. The abnormal 12−-cycles in blue Theorem 1.5 (Liu and Li [11]). Every planar graph without adjacent cycles of length at most 8 is 3- choosable. The first goal of this paper is to further improve Theorem 1.4 to the following result by allowing adjacent cycles of length 6 to 8 and changing the condition on precolored vertices from faces to cycles. But before we state the main theorem, it’s necessary to give a new conce… view at source ↗
Figure 2
Figure 2. A 5-face is adjacent to an 8 −-face, where the blue cycle bounds a 5-face and the red cycle bounds an 8 −-face Lemma 2.3. There are no 3-faces adjacent to 8 −-faces, no 4-faces adjacent to 6 −-faces, and no adjacent 5-faces. Proof. Recall that every face is bounded by a cycle. Assume that f is an 8 −-face and it is adjacent to a 5 −-face g. By Lemma 2.1, it suffices to consider that g is a 4- or 5-face. Suppose that… view at source ↗
Figure 3
Figure 3. A case in Lemma 2.5 any e 6= x1x2, so we may assume that φ 0 (x1) = 1, φ 0 (x2) = 2 and (x1, 1)(x2, 2) ∈ Mx1x2 . If (x1, 1) has an incident edge in Mx1x3 and (x2, 2) has an incident edge in Mx2x3 , then the closed walk x3x1x2 is not consistent in M, a contradiction. If (x1, 1) has no incident edge in Mx1x3 , then we can modify φ 0 to obtain an M-coloring of G by recoloring x2 and x3 in order, a contradiction. So we … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    O. V. Borodin, Colorings of plane graphs: A survey, Discrete Math. 313 (4) (2013) 517–539

    work page 2013

  2. [2]

    L. Chen, R. Liu, G. Yu, R. Zhao and X. Zhou, DP-4-colorability of two classes of planar graphs, Discrete Math. 342 (11) (2019) 2984–2993

    work page 2019

  3. [3]

    Dvořák, B

    Z. Dvořák, B. Lidický and R. Škrekovski, Planar graphs without 3-, 7-, and 8-cycles are 3-choosable, Discrete Math. 309 (20) (2009) 5899–5904

    work page 2009

  4. [4]

    Dvořák, B

    Z. Dvořák, B. Lidický and R. Škrekovski, 3-choosability of triangle-free planar graphs with constraints on 4-cycles, SIAM J. Discrete Math. 24 (3) (2010) 934–945

    work page 2010

  5. [5]

    Dvořák and L

    Z. Dvořák and L. Postle, Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8, J. Combin. Theory Ser. B 129 (2018) 38–54

    work page 2018

  6. [6]

    Grötzsch, Zur Theorie der diskreten Gebilde

    H. Grötzsch, Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 8 (1959) 109–120

    work page 1959

  7. [7]

    Kawarabayashi and C

    K.-i. Kawarabayashi and C. Thomassen, Decomposing a planar graph of girth 5 into an independent set and a forest, J. Combin. Theory Ser. B 99 (4) (2009) 674–684

    work page 2009

  8. [8]

    Kim and K

    S.-J. Kim and K. Ozeki, A note on a Brooks’ type theorem for DP-coloring, J. Graph Theory 91 (2) (2019) 148–161

    work page 2019

Show all 22 references
  1. [9]

    Li and T

    R. Li and T. Wang, DP-4-coloring of planar graphs with some restrictions on cycles, arXiv:1909.08511, https://arxiv.org/abs/1909.08511

    1909 arXiv

  2. [10]

    Li and T

    R. Li and T. Wang, Variable degeneracy on toroidal graphs, arXiv:1907.07141,https://arxiv.org/ abs/1907.07141

    1907 arXiv

  3. [11]

    R.LiuandX.Li, Everyplanargraphwithoutadjacentcyclesoflengthatmost8is3-choosable, European J. Combin. 82 (2019) 102995

    2019

  4. [12]

    R. Liu, X. Li, K. Nakprasit, P. Sittitrai and G. Yu, DP-4-colorability of planar graphs without adjacent cycles of given length, Discrete Appl. Math. 277 (2020) 245–251

    2020

  5. [13]

    R. Liu, S. Loeb, M. Rolek, Y. Yin and G. Yu, DP-3-coloring of planar graphs without 4, 9-cycles and cycles of two lengths from{6, 7, 8}, Graphs Combin. 35 (3) (2019) 695–705

    2019

  6. [14]

    R. Liu, S. Loeb, Y. Yin and G. Yu, DP-3-coloring of some planar graphs, Discrete Math. 342 (1) (2019) 178–189

    2019

  7. [15]

    Liu and G

    R. Liu and G. Yu, Planar graphs without short even cycles are near-bipartite, Discrete Appl. Math. 284 (2020) 626–630

    2020

  8. [16]

    F. Lu, Q. Wang and T. Wang, Cover and variable degeneracy, arXiv:1907.06630,https://arxiv.org/ abs/1907.06630

    1907 arXiv

  9. [17]

    X. Luo, M. Chen and W. Wang, On 3-colorable planar graphs without cycles of four lengths, Inform. Process. Lett. 103 (4) (2007) 150–156

    2007

  10. [18]

    Thomassen, Every planar graph is5-choosable, J

    C. Thomassen, Every planar graph is5-choosable, J. Combin. Theory Ser. B 62 (1) (1994) 180–181. 17

    1994

  11. [19]

    Thomassen,3-list-coloring planar graphs of girth5, J

    C. Thomassen,3-list-coloring planar graphs of girth5, J. Combin. Theory Ser. B 64 (1) (1995) 101–107

    1995

  12. [20]

    Wang and M

    W. Wang and M. Chen, On 3-colorable planar graphs without prescribed cycles, Discrete Math. 307 (22) (2007) 2820–2825

    2007

  13. [21]

    Wang and M

    W. Wang and M. Chen, Planar graphs without4, 6, 8-cycles are 3-colorable, Sci. China Ser. A 50 (11) (2007) 1552–1562

    2007

  14. [22]

    Yin and G

    Y. Yin and G. Yu, Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable, Discrete Math. 342 (8) (2019) 2333–2341. Appendix Proof of Lemma 3.2.(a) Suppose to the contrary thatS = V (G). Every IF-coloring ofG[S] is an IF- coloring ofG, a contradi...

    2019

Pith tools

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