pith. sign in

arxiv: 2605.23647 · v1 · pith:GWWRUKSJnew · submitted 2026-05-22 · 🧮 math.CO

Flexible DP-4-coloring of planar graphs without 4-cycles and intersecting triangles

Shu Fang , Runrun Liu , Gexin Yu This is my paper

Pith reviewed 2026-05-25 04:01 UTC · model grok-4.3

classification 🧮 math.CO
keywords planar graphsDP-coloringflexible coloring4-coloringno 4-cyclesintersecting triangleschoosabilityweighted coloring
0
0 comments X

The pith

Every simple planar graph without 4-cycles and intersecting triangles is weighted ε-flexibly DP-4-colorable.

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

The paper proves that every simple planar graph with neither 4-cycles nor triangles that share a vertex admits a weighted ε-flexible DP-4-coloring for some positive ε. This relaxes the triangle separation condition used in prior list-coloring results while upgrading the guarantee to the stronger DP-coloring model that incorporates correspondence edges and vertex weights. A reader would care because the flexibility condition ensures that a positive fraction of any given set of color preferences can still be satisfied even when not every preference is possible. The list size 4 is shown to be tight by an existing construction of a non-3-choosable planar graph that also avoids 4-cycles and intersecting triangles.

Core claim

Every simple planar graph without 4-cycles and without intersecting triangles is weighted ε-flexibly DP-4-colorable. The result improves on earlier work by replacing the stronger 3-cycle distance-at-least-2 hypothesis with the weaker condition that all triangles are vertex-disjoint, while extending the conclusion from ordinary list flexibility to the weighted DP setting.

What carries the argument

weighted ε-flexible DP-4-coloring, which requires that for any 4-list assignment equipped with a correspondence matching and any request function on a subset of vertices, there exists a proper DP-coloring that satisfies at least ε times the total weight of the requested vertices.

If this is right

  • Any such graph has a DP-4-coloring that meets at least an ε-fraction of arbitrary color preferences under any correspondence matching.
  • The 4-list size is best possible because there exist planar graphs avoiding 4-cycles and intersecting triangles that are not 3-choosable.
  • The vertex-disjoint-triangles condition is strictly weaker than the previous distance-2 condition on triangles while still supporting the flexibility result.
  • The weighted version directly implies the unweighted case by setting all weights equal.

Where Pith is reading between the lines

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

  • The same structural hypothesis may suffice for analogous flexibility statements in other coloring models such as online or paintability.
  • It is plausible that the result extends to graphs embeddable on surfaces of higher genus under the same forbidden-subgraph conditions.
  • An algorithmic consequence would be a polynomial-time method to produce a coloring satisfying a guaranteed positive fraction of preferences whenever the input graph meets the hypotheses.

Load-bearing premise

The structural condition that no two triangles share a vertex is enough to make the inductive or discharging argument carry over from the earlier list-coloring theorem to the weighted DP-flexibility setting.

What would settle it

A concrete planar graph with no 4-cycles, with only vertex-disjoint triangles, and with a 4-list assignment plus request set such that no DP-coloring satisfies more than an arbitrarily small fraction of the requested weight.

Figures

Figures reproduced from arXiv: 2605.23647 by Gexin Yu, Runrun Liu, Shu Fang.

Figure 1
Figure 1. Figure 1: examples of (RC2)-(RC8) Note that (FORB) of Definition 2.1 in particular implies that k − dG + d(S−B) ≥ 2 for all v ∈ V (S). So in the proofs of Lemmas 3.1 to 3.9 below, the case |I| = 1 in (FORB) is implied by (FIX). Therefore by Lemma 2.4, we only need to check the cases for (FIX) and for |I| = 2 in (FORB) in order to prove Lemmas 3.1 to 3.9. Lemmas 3.1 and 3.2 are from [5], we include the proofs here fo… view at source ↗
Figure 2
Figure 2. Figure 2: k1-, k2- and 43-vertices For convenience, we call f a pendent 5-face of v if f is adjacent to a 3-face containing v and v is not on f; in this case we call v a weakly incident vertex of f. A 5+-vertex v is special if v has at most d(v) − 5 pendent 3-faces. A 4+-vertex v is heavy if v is a 5+-vertex with exactly d(v) − 4 pendent 3-faces or a 4-vertex with no incident 3-face and no pendent 3-face. A 4+-verte… view at source ↗
Figure 3
Figure 3. Figure 3: two typical structures in (RC9), f in the left one is a poor 5-face satis￾fying (i) and f in the right one is a poor 5-face satisfying (ii). v2 is a 43-vertex. Then one of v4, v5 is a 4+-vertex v with d(v) − 3 pendent 3-faces. If v4 is such a vertex, then applying Lemma 3.8 to the path v1v2v3v4 gives a contradiction; if v5 is such a vertex, then applying Lemma 3.8 to the path v3v2v1v5 gives a contradiction… view at source ↗
read the original abstract

Graph coloring with preferences offers a powerful framework for constraint satisfaction problems in which fulfilling every request is impossible but satisfying a guaranteed positive fraction is highly desirable. A \emph{request} on a graph $G$ equipped with a list assignment $L$ assigns to each vertex of some subset $dom(r)\subseteq V(G)$ a preferred color from its list. Following Dvo\v{r}\'{a}k, Norin, and Postle (2019), $G$ is \emph{$\varepsilon$-flexibly $k$-choosable} if, for every $k$-list assignment $L$ and every request $r$, there is an $L$-coloring of $G$ that agrees with $r$ on at least $\varepsilon|dom(r)|$ vertices. The corresponding notion for DP-coloring (correspondence coloring) was formalized by Bradshaw, Choi, and Kostochka (2025). Choi, Clemen, Ferrara, Horn, Ma, and Masa\v{r}\'{i}k (2022) proved that every planar graph without $4$-cycles and with $3$-cycle distance at least $2$ is $\varepsilon$-flexibly $4$-choosable. We improve the result in two respects: weakening the hypothesis from $3$-cycle distance $\geq 2$ to vertex-disjoint triangles, and strengthening the conclusion from list flexibility to weighted DP-flexibility: \emph{Every simple planar graph without $4$-cycles and without intersecting triangles is weighted $\varepsilon$-flexibly DP-$4$-colorable.} The list size $4$ is sharp: Montassier, Raspaud, and Wang constructed a planar graph without $4$-cycles, $5$-cycles, and intersecting triangles that is not $3$-choosable.

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

0 major / 2 minor

Summary. The paper proves that every simple planar graph without 4-cycles and without intersecting triangles (i.e., vertex-disjoint triangles) is weighted ε-flexibly DP-4-colorable. This strengthens the ε-flexible 4-choosability result of Choi et al. (2022) by relaxing the triangle separation hypothesis from distance at least 2 to vertex-disjoint triangles and by extending the conclusion from list coloring to the weighted DP-coloring (correspondence coloring) setting. The bound of 4 is shown to be sharp by citing the Montassier-Raspaud-Wang construction of a planar graph without 4-cycles, 5-cycles, and intersecting triangles that is not 3-choosable.

Significance. If the result holds, it meaningfully advances the theory of flexible coloring by moving from choosability to the strictly stronger DP framework while simultaneously enlarging the class of admissible graphs. The weighted formulation adds practical robustness. Credit is due for the parameter-free nature of the statement and for the explicit sharpness example that matches the hypothesis exactly.

minor comments (2)
  1. The abstract cites Bradshaw et al. (2025) for the definition of weighted DP-flexibility; the introduction should include a self-contained one-paragraph recap of the weighted request model to aid readers unfamiliar with the 2025 paper.
  2. Notation for the weight function w and the flexibility parameter ε should be introduced once in a dedicated preliminary subsection rather than scattered across the statement of the main theorem.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our work, as well as for the recommendation to accept the manuscript.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper extends the external choosability result of Choi et al. (2022) by relaxing the triangle-distance hypothesis to vertex-disjoint triangles and upgrading the conclusion to weighted DP-flexibility, citing the independent definition from Bradshaw et al. (2025). No self-citations appear, no parameters are fitted to the target statement, and the central claim does not reduce by definition or construction to its inputs. The listed sharpness example is also external. The derivation chain is therefore self-contained against the cited benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The theorem rests on the standard definitions of planar graphs, list assignments, requests, DP-coloring, and weighted flexibility as introduced in the cited papers; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard axioms and definitions of graph theory, planarity, cycles, and coloring (including DP-coloring as formalized by Bradshaw et al. 2025)
    The statement is a theorem within these established frameworks; the abstract invokes them implicitly when defining ε-flexible DP-4-colorability.

pith-pipeline@v0.9.0 · 5866 in / 1216 out tokens · 23915 ms · 2026-05-25T04:01:26.354028+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

16 extracted references · 16 canonical work pages

  1. [1]

    R. Bi, P. Bradshaw, Flexible list coloring of graphs with maximum average degree less than 3, arXiv:2310.02979

    work page arXiv

  2. [2]

    Bradshaw, I

    P. Bradshaw, I. Choi, A. Kostochka, Flexible DP 3-coloring of sparse multigraphs, arXiv:2510.13043

    work page arXiv

  3. [3]

    Bradshaw, T

    P. Bradshaw, T. Masaˇ r´ ık, L. Stacho, Flexible list colorings in graphs with special degeneracy conditions, J. Graph Theory, 101 (4) (2022) 717–745. 15

    work page 2022

  4. [4]

    Cambie, W

    S. Cambie, W. Cames van Batenburg, X. Zhu, Disjoint list-colorings for planar graphs, arXiv:2312.17233

    work page arXiv

  5. [5]

    I. Choi, F. C. Clemen, M. Ferrara, P. Horn, F. Ma and T. Masaˇ r´ ık, Flexibility of planar graphs— Sharpening the tools to get lists of size four, Discrete Appl. Math., 306 (2022) 120–132

    work page 2022

  6. [6]

    Dvoˇ r´ ak, T

    Z. Dvoˇ r´ ak, T. Masaˇ r´ ık, J. Mus´ ılek, O. Pangr´ ac, Flexibility of planar graphs of girth at least six, J. Graph Theory, 95 (3) (2020) 457–466

    work page 2020

  7. [7]

    Dvoˇ r´ ak, T

    Z. Dvoˇ r´ ak, T. Masaˇ r´ ık, J. Mus´ ılek, O. Pangr´ ac, Flexibility of triangle-free planar graphs, J. Graph Theory, 96 (4) (2021) 619–641

    work page 2021

  8. [8]

    Dvoˇ r´ ak, S

    Z. Dvoˇ r´ ak, S. Norin, L. Postle, List coloring with requests, J. Graph Theory, 92 (3) (2019) 191–206

    work page 2019

  9. [9]

    Dvoˇ r´ ak, L

    Z. Dvoˇ r´ ak, 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

  10. [10]

    H. Kaul, R. Mathew, J. A. Mudrock, M. J. Pelsmajer, Flexible list colorings: Maximizing the number of requests satisfied, J. Graph Theory, 106 (4) (2024) 887–906

    work page 2024

  11. [11]

    P. C. B. Lam, B. Xu, J. Liu, The 4-choosability of plane graphs without 4-cycles, J. Combin. Theory Ser. B, 76 (1) (1999) 117–126

    work page 1999

  12. [12]

    Masaˇ r´ ık, Flexibility of planar graphs without 4-cycles, Acta Math

    T. Masaˇ r´ ık, Flexibility of planar graphs without 4-cycles, Acta Math. Univ. Comenian. (N.S.) 88 (3) (2019) 935–940

    work page 2019

  13. [13]

    Montassier, A

    M. Montassier, A. Raspaud, W. Wang, Bordeaux 3-color conjecture and 3-choosability, Dis- crete Math., 306 (6) (2006) 573–579

    work page 2006

  14. [14]

    W. Wang, K. Lih, Choosability and edge choosability of planar graphs without intersecting triangles, SIAM J. Discrete Math. 15 (4) (2002) 538–545

    work page 2002

  15. [15]

    D. Yang, F. Yang, Flexibility of planar graphs withoutC 4 andC 5, Discrete Appl. Math., 380 (2026) 228–246

    work page 2026

  16. [16]

    Yang, On sufficient conditions for planar graphs to be 5-flexible, Graphs Combin

    F. Yang, On sufficient conditions for planar graphs to be 5-flexible, Graphs Combin. 38 (3) (2022) 70. 16

    work page 2022