pith. sign in

arxiv: 2604.13212 · v2 · submitted 2026-04-14 · 🧮 math.CO

Fractional Strict Degeneracy of Graphs

Daniel Dominik , Jeffrey A. Mudrock This is my paper

Pith reviewed 2026-05-10 14:28 UTC · model grok-4.3

classification 🧮 math.CO
keywords fractional DP-coloringDP-chromatic numberfractional degeneracyunicyclic graphsbipartite graphssparse graphslist coloringdegeneracy
0
0 comments X

The pith

Two fractional analogues of graph degeneracy upper-bound the fractional DP-chromatic number.

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

The paper defines two new measures that adapt the classical notion of graph degeneracy to a fractional setting. Each measure is shown to serve as an upper bound on the fractional DP-chromatic number of any graph. The authors then apply the measures to derive explicit bounds for unicyclic graphs, certain complete bipartite graphs, and sparse graphs. This approach mirrors earlier degeneracy-based results for ordinary DP-chromatic numbers but operates in the fractional DP-coloring framework introduced by Bernshteyn, Kostochka, and Zhu.

Core claim

We introduce two analogues of the degeneracy of a graph to the fractional context, each of which bound its fractional DP-chromatic number from above. We use these analogues to bound the fractional DP-chromatic number of a variety of graphs including unicyclic graphs, some complete bipartite graphs, and sparse graphs.

What carries the argument

Two fractional degeneracy analogues, each defined to upper-bound the fractional DP-chromatic number of a graph.

If this is right

  • The fractional DP-chromatic number of every unicyclic graph is bounded above by one of the new fractional degeneracy values.
  • Explicit upper bounds on the fractional DP-chromatic number hold for certain complete bipartite graphs via the fractional degeneracy measures.
  • Sparse graphs receive improved fractional DP-chromatic number bounds from the new measures.
  • The fractional DP-coloring framework now admits degeneracy-style arguments analogous to those already used for ordinary DP-coloring.

Where Pith is reading between the lines

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

  • The same fractional degeneracy ideas could be tested on other families such as planar graphs or graphs with bounded treewidth to see whether they yield sharper bounds than existing techniques.
  • If the two measures coincide on many graphs, one of them might turn out to be the more natural or computable parameter for future work.
  • These bounds may help classify when fractional DP-coloring behaves similarly to ordinary fractional coloring.

Load-bearing premise

The two newly defined fractional degeneracy measures are well-defined and correctly serve as upper bounds on the fractional DP-chromatic number.

What would settle it

A concrete graph whose fractional DP-chromatic number exceeds the value given by either of the two new fractional degeneracy measures would falsify the bounding claims.

Figures

Figures reproduced from arXiv: 2604.13212 by Daniel Dominik, Jeffrey A. Mudrock.

Figure 1
Figure 1. Figure 1: Pictorial illustration of an application of the [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Pictorial illustration of the (G, S, T)-legal sequence S = (s1, s2, s3) where G = C4, S(v) = 3, and T(v) = 2. Suppose j ∈ [3]. For the diagram to the left of the arrow corresponding to sj , the ordered pair next to each vertex is (Sj (vi), Tj (vi)) for each i ∈ [4]. The right-most diagram is a pictorial illustration of the final output of S (note that v4 has been removed from G3 by s3). when S is a complet… view at source ↗
Figure 3
Figure 3. Figure 3: Each (i) is a pictorial illustration of G (2) i along with the ordered pairs (S (2) i , T(2) i ). Notice that (2), (3), (4) correspond to outputs of the operations of S (2) when G = C6 and t = 2 as described in Theorem 7. We now present a tool that will be of great importance in the proofs of Theorems 8 and 10. Lemma 29. For r ∈ N, suppose G = P2r−1 and the vertices of G in order are v1, . . . , v2r−1. Sup… view at source ↗
Figure 4
Figure 4. Figure 4: In the proof of Lemma 29 when G = P5 we know that µ ∈ [5]. In the case µ = 5, G(5) is edgeless. For each of the other possible cases, the figure provides pictorial illustrations of G (µ) i along with the ordered pairs (S (µ) i , T(µ) i ) for the operations of S (µ) . Proof. It is well known that χ ∗ (C2r+1) = 2 + 1/r (see e.g., [1]) which means ST (4)∗ (C2r+1) ≥ 2 + 1/r. To prove our result, we show ST (4)… view at source ↗
Figure 5
Figure 5. Figure 5: Each (i) is a pictorial illustration of Gi along with the ordered pairs (Si , Ti). Notice that (2), (3), (4), (5), (6), and (7) correspond to the outputs of the operations of S when G = C7 as described in the proof of Theorem 8. Recall that Zhou, Zhu, and Zhu [22] showed that the Alon-Tarsi number of a graph G is a lower bound on ST(1)(G). So, we have AT(G) ≤ ST (3)(G). Notice Theorem 8 shows that the Alon… view at source ↗
Figure 6
Figure 6. Figure 6: Each (i) is a pictorial illustration of G (2) i along with the ordered pairs (S (2) i , T(2) i ). Notice that (2), (3), (4), (5), (6), and (7) correspond to the outputs of the operations of S (2) when G = K2,3 as described in the proof of Theorem 9. As stated before, Theorem 9 leads to a few of the best known upper bounds on certain fractional DP-chromatic numbers. Recall that based on the results from [7]… view at source ↗
read the original abstract

DP-coloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvo\v{r}\'{a}k and Postle in 2015. The DP-chromatic number of a graph $G$, $\chi_{_{DP}}(G)$, is the analogue of the chromatic number of $G$ in the DP context and is bounded above by the degeneracy of $G$ plus one. Over the last two years a plethora of authors have introduced variations on the notion of degeneracy and used these new ideas to give improved bounds on the DP-chromatic number of certain families of graphs. Fractional DP-coloring is a generalization of fractional list coloring introduced by Bernshteyn, Kostochka, and Zhu in 2019. In this paper we introduce two analogues of the degeneracy of a graph to the fractional context, each of which bound its fractional DP-chromatic number from above. We use these analogues to bound the fractional DP-chromatic number of a variety of graphs including unicyclic graphs, some complete bipartite graphs, and sparse graphs.

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 introduces two new fractional analogues of graph degeneracy (likely via weighted or LP-based relaxations of minimum-degree orderings) and proves that each upper-bounds the fractional DP-chromatic number. These measures are then applied to derive explicit bounds on the fractional DP-chromatic number for unicyclic graphs, selected complete bipartite graphs, and sparse graphs.

Significance. If the central claims hold, the work supplies new, potentially tighter tools for bounding fractional DP-chromatic numbers by extending classical degeneracy ideas into the fractional DP-coloring setting. The applications to concrete families (unicyclic, bipartite, sparse) demonstrate utility and could stimulate further use of fractional degeneracy parameters in coloring theory.

minor comments (2)
  1. The abstract states that the new measures 'bound its fractional DP-chromatic number from above' but does not indicate whether the bounds are tight or how they compare quantitatively to existing degeneracy-based bounds; adding a sentence with the strongest concrete bound obtained would improve clarity.
  2. Notation for the two new parameters (e.g., fractional degeneracy vs. fractional strict degeneracy) should be introduced with a short comparison table or explicit definitions in the introduction to help readers track which measure is used in each application.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including the recognition that the two new fractional degeneracy analogues provide potentially tighter tools for bounding fractional DP-chromatic numbers, with demonstrated utility on unicyclic graphs, selected complete bipartite graphs, and sparse graphs. We appreciate the recommendation for minor revision.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper introduces two novel fractional analogues of degeneracy and proves they upper-bound the fractional DP-chromatic number for unicyclic graphs, selected complete bipartite graphs, and sparse graphs. No load-bearing derivation step, equation, or self-citation is visible that reduces any claimed bound to a tautology, a fitted parameter renamed as a prediction, or an imported uniqueness result from the authors' prior work. The central claims rest on explicit definitions and independent bounding arguments rather than self-referential construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no explicit free parameters, axioms, or invented entities can be identified.

pith-pipeline@v0.9.0 · 5476 in / 1018 out tokens · 14412 ms · 2026-05-10T14:28:44.896175+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

22 extracted references · 22 canonical work pages

  1. [1]

    N. Alon, Z. Tuza, and M. Voigt. Choosability and fractional chromatic number.Discrete Mathematics, 165–166:31–38, 1997

    work page 1997

  2. [2]

    Bernshteyn

    A. Bernshteyn. Weak degeneracy of graphs. Talk at Illinois Institute of Technology, April 2022. Unpublished talk

    work page 2022

  3. [3]

    Bernshteyn, A

    A. Bernshteyn, A. Kostochka, and X. Zhu. Fractional DP-colorings of sparse graphs. Journal of Graph Theory, 39:203–221, 2020

    work page 2020

  4. [4]

    Bernshteyn and E

    A. Bernshteyn and E. Lee. Weak degeneracy of graphs.Journal of Graph Theory, 103:607–634, 2023

    work page 2023

  5. [5]

    Bernshteyn, E

    A. Bernshteyn, E. Lee, and E. Smith-Roberge. Weak degeneracy of planar graphs, 2025. https://arxiv.org/abs/2406.02792

    work page arXiv 2025

  6. [6]

    Bradshaw and J

    P. Bradshaw and J. Zeng. Paintability ofr-chromatic graphs.Discrete Mathematics, 348, 2025. 114558

    work page 2025

  7. [7]

    Dominik, H

    D. Dominik, H. Kaul, and J Mudrock. A note on fractional DP-coloring of graphs. Discrete Mathematics, 347, 2024. 114123

    work page 2024

  8. [8]

    PhD thesis, Illinois Institute of Technology, 2025

    Daniel Dominik.Random and Fractional Perspectives on DP-Coloring of Graphs. PhD thesis, Illinois Institute of Technology, 2025

    work page 2025

  9. [9]

    Dvoˇ r´ ak and L

    Z. Dvoˇ r´ ak and L. Postle. Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8.Journal of Combinatorial Theory, Series B, 129:38–54, 2018

    work page 2018

  10. [10]

    Dvoˇ r´ ak, X

    Z. Dvoˇ r´ ak, X. Hu, and H.-S. Sereni. A 4-choosable graph that is not (8 : 2)-choosable. Advances in Combinatorics, 2019.https://doi.org/10.19086/aic.10811

    work page doi:10.19086/aic.10811 2019

  11. [11]

    Erd˝ os, L

    P. Erd˝ os, L. Rubin, and H. Taylor. Choosability in graphs.Proc. West Coast Confer- ence on Combinatorics, Graph Theory and Computing, Congressus Numerantium XXVI, 26:125–157, 1979

    work page 1979

  12. [12]

    M. Han, J. He, and X. Zhu. Weak degeneracy of the square of line graphs.Advances in Mathematics (China), 04:720–730, 2024

    work page 2024

  13. [13]

    Kaul and J

    H. Kaul and J. Mudrock. On the Alon-Tarsi number and chromatic-choosability of cartesian products of graphs.The Electronic Journal of Combinatorics, 26, 2019. P1.3

    work page 2019

  14. [14]

    Kaul and J

    H. Kaul and J. Mudrock. Combinatorial nullstellensatz and DP-coloring of graphs. Discrete Mathematics, 324, 2020. 112115. 28

    work page 2020

  15. [15]

    Hemanshu Kaul and Jeffrey A. Mudrock. A note on fractional DP-coloring of graphs, 2020.https://arxiv.org/abs/1910.03416v1

    work page arXiv 2020

  16. [16]

    Misra, G

    N. Misra, G. Philip, V. Raman, and S. Saurabh. On parameterized independent feedback vertex set.Theoretical Computer Science, 461:65–75, 2012

    work page 2012

  17. [17]

    Scheinerman and D.H

    E.R. Scheinerman and D.H. Ullman.Fractional Graph Theory. John Wiley & Sons, 1997.https://www.ams.jhu.edu/ers/wp-content/uploads/2015/12/fgt.pdf

    work page 1997

  18. [18]

    Tuza and M

    Z. Tuza and M. Voigt. Every 2-choosable graph is (2m, m)-choosable.Journal of Graph Theory, 22:245–252, 1996

    work page 1996

  19. [19]

    V.G. Vizing. Coloring the vertices of a graph in prescribed colors (in Russian).Diskret. Analiz., 29:3–10, 1976

    work page 1976

  20. [20]

    D. B. West.Introduction to Graph Theory. Prentice Hall, Upper Saddle River, NJ, 2001

    work page 2001

  21. [21]

    Y. Yang. Weak degeneracy of regular graphs.Discrete Mathematics, 6, 2024. 114023

    work page 2024

  22. [22]

    H. Zhou, J. Zhu, and X. Zhu. Arc-weighted acyclic orientations of variations of degen- eracy of graphs, 2024.https://arxiv.org/abs/2308.15853. A Appendix We use the framework described in Remark 28 to complete the proof of Theorem 7. Claim 33.Using the notation established in the proof of Theorem 7,S (1) hasrterms,S (1) is a restricted(G, S (1), T(1))-leg...

    work page arXiv 2024