pith. sign in

arxiv: 2605.17783 · v1 · pith:NA37T6V2new · submitted 2026-05-18 · 🧮 math.CO

An introduction to equitable DP coloring of graphs

H. A. Kierstead , Alexandr Kostochka , Zimu Xiang This is my paper

Pith reviewed 2026-05-20 09:56 UTC · model grok-4.3

classification 🧮 math.CO
keywords equitable coloringDP-coloringlist coloringgraph coloringcolor class sizecorrespondence assignmentchromatic number
0
0 comments X

The pith

Equitable DP-coloring extends the size-balance rule of equitable coloring to correspondence assignments in DP-coloring.

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

The paper defines an equitable k-DP-coloring of an n-vertex graph as a proper DP-coloring from a k-correspondence assignment in which every color class has size at most ceil(n/k). This mirrors the recent extension of equitable coloring to the list-coloring setting but uses the more general DP framework based on matchings between color sets rather than direct lists. A sympathetic reader would care because the size constraint adds a balance condition useful for applications such as scheduling, while the DP model already strengthens ordinary list coloring. The authors examine basic properties of the resulting equitable DP-chromatic number as a graph parameter.

Core claim

An equitable k-DP-coloring is a proper coloring arising from a k-correspondence assignment on the vertices such that each color appears in at most ceil(n/k) vertices. The paper introduces this definition as a direct extension of both equitable coloring and DP-coloring and begins the study of its properties, including relations to the ordinary DP-chromatic number.

What carries the argument

Equitable DP-coloring: a proper DP-coloring (via correspondence assignment and matchings) subject to the additional constraint that no color class exceeds size ceil(n/k).

If this is right

  • The equitable DP-chromatic number is at least the DP-chromatic number for every graph.
  • Equitable DP-coloring generalizes equitable list coloring because every list assignment is a special case of a correspondence assignment.
  • Standard monotonicity and hereditary properties of coloring parameters continue to hold under the new definition.
  • Existence results for large enough k follow from the corresponding results for DP-coloring combined with the size bound.

Where Pith is reading between the lines

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

  • One could test whether the equitable DP-chromatic number coincides with the DP-chromatic number on trees or bipartite graphs.
  • The framework suggests looking for equitable versions of known DP-coloring theorems for planar or sparse graphs.
  • Algorithmic questions arise about efficiently finding a balanced proper DP-coloring when one exists.

Load-bearing premise

The size-balance condition can be imposed directly on DP-colorings by limiting each color class to at most ceil(n/k) without breaking the correspondence matching structure.

What would settle it

A concrete n-vertex graph G, integer k, and k-correspondence assignment that admits a proper DP-coloring but every such coloring has at least one color class larger than ceil(n/k), even though G admits an equitable k-list-coloring.

Figures

Figures reproduced from arXiv: 2605.17783 by Alexandr Kostochka, H. A. Kierstead, Zimu Xiang.

Figure 2.1
Figure 2.1. Figure 2.1: Paths are not EDP 2-colorable. 1.6. Notation. Let G and H be graphs. Set G ∨ H = G ∪ H ∪ K(V (G), V (H)). Let G be the complement of G. Let G + H be the union of disjoint copies of G and H. Let Kn be the complete graph on n vertices. Let K(X) be the complete graph with vertex set X or {X} depending on whether X is a set or a list. Similarly, K(X, Y ) := K(X)∨K(Y ). Let Pn be the path on n vertices and Cn… view at source ↗
Figure 2.2
Figure 2.2. Figure 2.2: C4 is not SEDP 3-colorable witnessed by the cover H. (c) C6 is not EDP 3-colorable. Proof. For (a), suppose n = 3. Let H3 be the plain 3-cover for C3 with H3(vi , vi⊕1) := (1 2)(3) for all i ∈ [3]. Any H3-coloring of C3 must only use two colors, and so is not ⌈ |C3| 3 ⌉-bounded. Similarly, let H4 be the plain 4-cover for C3 such that H4(vi , vi⊕1) := (1 2)(3 4) for all i ∈ [3]. Any H4-coloring must only … view at source ↗
Figure 2.3
Figure 2.3. Figure 2.3: Forests T (left) and F3 (right) are not EDP 3-colorable. Every forest G is DP 2-colorable and equitably (⌈ ∆(G) 2 ⌉ + 1)-colorable. By Theorem 2, every n-vertex forest with maximum degree at most n+8 3 is equitably 3-colorable. However: Example 3 (Forests). (a) The tree T := u1uu2 ∪ v1vv2 ∪ uv (a balanced double star) is not EDP 3-colorable; (b) for all k ≥ 1, the forest Fk := K(u; u1, . . . uk+1) + P i∈… view at source ↗
Figure 2.4
Figure 2.4. Figure 2.4: G7,3 = K(D) ∨ K(S) is not equitably H-colorable, where H is the 8-cover for G7,3 with H(u, v) = (1 2)(3 4)(5 6)(7 8) for all edges uv ∈ G7,3. If H(u, v)(f(v)) = f(v) then f(v) = k and k is odd. Thus after coloring D, there are at most k − 2d + (k mod 2) ≤ n − d − 1 colors left for the n − d vertices in S, a contradiction. □ Proposition 5 below implies that for all n > d ≥ 0 every n-vertex d-degenerate gr… view at source ↗
read the original abstract

A proper $k$-coloring of vertices of an $n$-vertex graph is equitable if the size of every color class is $\lfloor n/k\rfloor$ or $\lceil n/k\rceil$. An extension of it to list coloring requires only that the size of every color class is at most $\lceil n/k\rceil$. Such colorings have interesting applications and have been actively studied recently. In this paper, we extend the notion of equitable coloring to the more general notion of equitable DP coloring and study properties of the new parameter.

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

1 major / 3 minor

Summary. The manuscript introduces equitable DP-coloring as a definitional extension of equitable coloring into the DP-coloring framework. A proper DP-coloring is equitable if the selected color classes from the DP-cover satisfy the size-balance condition (each of size floor(n/k) or ceil(n/k), or at most ceil(n/k) in the list-coloring case). The paper studies basic properties of the resulting equitable DP-chromatic number, including its relationship to the ordinary DP-chromatic number and equitable chromatic number.

Significance. If the properties are correctly established, the work supplies a natural common generalization of two actively studied parameters. This could support future results on balanced resource allocation under correspondence constraints. The introductory nature means significance rests on whether the studied properties include nontrivial bounds, monotonicity results, or examples that distinguish the new parameter from its predecessors.

major comments (1)
  1. [§2] §2, Definition 2.1: The size-balance condition is imposed directly on the image of the matching from the DP-cover. The manuscript must verify that this does not force the selected matching to violate the properness condition of the DP-coloring when the cover is minimal; otherwise the parameter may be strictly larger than the DP-chromatic number even for graphs where equitable colorings exist.
minor comments (3)
  1. [Abstract] The abstract and introduction should explicitly state whether the equitable condition uses the floor/ceil partition or the weaker 'at most ceil(n/k)' version; the two are not interchangeable in the DP setting.
  2. [§1] Notation for the equitable DP-chromatic number (e.g., χ_eq^DP(G)) should be introduced once and used consistently; current usage mixes it with ordinary DP-chromatic number symbols.
  3. [§3] Examples in §3 would benefit from a small table comparing χ_eq(G), χ_DP(G), and χ_eq^DP(G) for a few graphs (cycles, complete graphs, bipartite graphs) to illustrate when the parameters differ.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the recommendation of minor revision. We address the single major comment below.

read point-by-point responses

  1. Referee: [§2] §2, Definition 2.1: The size-balance condition is imposed directly on the image of the matching from the DP-cover. The manuscript must verify that this does not force the selected matching to violate the properness condition of the DP-coloring when the cover is minimal; otherwise the parameter may be strictly larger than the DP-chromatic number even for graphs where equitable colorings exist.

    Authors: We appreciate the referee highlighting this definitional detail. By definition, an equitable DP-coloring requires the existence of a matching in the given DP-cover that is proper (i.e., satisfies the standard DP-coloring adjacency condition) and whose selected color classes additionally meet the size-balance condition. The properness requirement is imposed first and independently; the balance condition is applied only to those proper matchings. Consequently, the equitable DP-chromatic number is always at least the ordinary DP-chromatic number, and the two parameters coincide on graphs for which equitable colorings exist whenever the underlying DP-cover admits a proper matching of the required size. We will insert a short clarifying paragraph immediately after Definition 2.1 to make this separation explicit and to note that no proper matching is ever disqualified solely by the balance requirement. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper introduces the equitable DP-coloring parameter via a direct definitional extension of the size-balance condition (color classes of size floor(n/k) or ceil(n/k), or at most ceil(n/k) in the list case) from equitable coloring and list coloring to the DP-cover correspondence setting. No equations, quantitative predictions, or uniqueness theorems are asserted that reduce by construction to fitted inputs, self-citations, or prior ansatzes. The work is self-contained as an introductory study of basic properties of the new parameter; the size constraint is imposed directly on the DP-cover without altering the core matching structure, and no load-bearing claim relies on a self-referential loop or imported uniqueness result.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper rests on standard graph-theoretic definitions of proper coloring, equitable coloring, and DP-coloring; the main addition is the new combined parameter with no free parameters or invented physical entities.

axioms (1)
  • standard math Standard definitions of proper vertex coloring, equitable coloring, and DP-coloring (correspondence coloring) from prior literature.
    The abstract explicitly builds the new notion as an extension of these established concepts.
invented entities (1)
  • equitable DP coloring no independent evidence
    purpose: A new graph parameter requiring balanced color class sizes within the DP-coloring model.
    Introduced in the paper as the central new object of study.

pith-pipeline@v0.9.0 · 5612 in / 1099 out tokens · 33304 ms · 2026-05-20T09:56:55.891835+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

28 extracted references · 28 canonical work pages

  1. [1]

    Spanning subgraphs of random graphs.Graphs Combin., 8(1):91–94, 1992

    Noga Alon and Zoltán Füredi. Spanning subgraphs of random graphs.Graphs Combin., 8(1):91–94, 1992

    work page 1992

  2. [2]

    Noga Alon and Raphael Yuster.H-factors in dense graphs.J. Combin. Theory Ser. B, 66(2):269–282, 1996

    work page 1996

  3. [3]

    Springer Berlin, Heidelberg, 01 2001

    Jacek Blazewicz, Klaus Ecker, Erwin Pesch, Guenter Schmidt, and Jan Weglarz.Scheduling Computer and Manufacturing Processes. Springer Berlin, Heidelberg, 01 2001

    work page 2001

  4. [4]

    Béla Bollobás and Richard K. Guy. Equitable and proportional coloring of trees.J. Combin. Theory Ser. B, 34(2):177–186, 1983

    work page 1983

  5. [5]

    Gerard J. Chang. A note on equitable colorings of forests.European J. Combin., 30(4):809–812, 2009

    work page 2009

  6. [6]

    Equitable coloring of trees.J

    Bor-Liang Chen and Ko-Wei Lih. Equitable coloring of trees.J. Combin. Theory Ser. B, 61(1):83–87, 1994

    work page 1994

  7. [7]

    Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8.J

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

    work page 2018

  8. [8]

    T. Gallai. Kritische graphen i.Math. Inst. Hungar. Acad. Sci, 8:165–192 (in German), 1963

    work page 1963

  9. [9]

    Hajnal and E

    A. Hajnal and E. Szemerédi. Proof of a conjecture of P. Erdős. InCombinatorial theory and its appli- cations, II (Proc. Colloq., Balatonfüred, 1969), pages 601–623. North-Holland, Amsterdam, 1970

    work page 1969

  10. [10]

    Bounded vertex colorings of graphs.Discrete Math., 111(1-3):305–312, 1993

    Pierre Hansen, Alain Hertz, and Julio Kuplinsky. Bounded vertex colorings of graphs.Discrete Math., 111(1-3):305–312, 1993. Graph theory and combinatorics (Marseille-Luminy, 1990)

    work page 1993

  11. [11]

    Scheduling with conflicts, and applications to traffic signal control

    Sandy Irani and Vitus Leung. Scheduling with conflicts, and applications to traffic signal control. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 85–94, 01 1996

    work page 1996

  12. [12]

    The infamous upper tail.Random Structures & Algorithms, 20(3):317–342, 2002

    Svante Janson and Andrzej Ruciński. The infamous upper tail.Random Structures & Algorithms, 20(3):317–342, 2002

    work page 2002

  13. [13]

    H. A. Kierstead and A. V. Kostochka. Equitable list coloring of graphs with bounded degree.J. Graph Theory, 74(3):309–334, 2013

    work page 2013

  14. [14]

    H. A. Kierstead, Alexandr Kostochka, and Zimu Xiang. Equitable list coloring of planar graphs with given maximum degree.J. Graph Theory, 108(4):832–838, 2025

    work page 2025

  15. [15]

    H. A. Kierstead, Alexandr Kostochka, and Zimu Xiang. Results and problems on equitable coloring of graphs. InSum(m)it280: Surveys in Extremal Combinatorics and Combinatorial Geometry, volume 32 ofBolyai Society Mathematical Studies, pages ?–? Springer, 2026

    work page 2026

  16. [16]

    A. V. Kostochka, M. J. Pelsmajer, and D. B. West. A list analogue of equitable coloring.J. Graph Theory, 44(3):166–177, 2003

    work page 2003

  17. [17]

    Krarup and D

    J. Krarup and D. de Werra. Chromatic optimisation: Limitations, objectives, uses, references.European Journal of Operational Research, 11(1):1–19, 1982. Third EURO IV Special Issue

    work page 1982

  18. [18]

    Equitable coloring.Amer

    Walter Meyer. Equitable coloring.Amer. Math. Monthly, 80:920–922, 1973

    work page 1973

  19. [19]

    Miyata, S

    D. Miyata, S. Tokunaga, and A. Kaneko. Equitable coloring of trees. unpublished

    work page

  20. [20]

    Equitable colorings of planar graphs with maximum degree at least nine.Discrete Math., 312(5):1019–1024, 2012

    Kittikorn Nakprasit. Equitable colorings of planar graphs with maximum degree at least nine.Discrete Math., 312(5):1019–1024, 2012

    work page 2012

  21. [21]

    Pelsmajer

    Michael J. Pelsmajer. Equitable list-coloring for graphs of maximum degree 3.J. Graph Theory, 47(1):1– 8, 2004

    work page 2004

  22. [22]

    Pemmaraju

    Sriram V. Pemmaraju. Equitable coloring extends Chernoff-Hoeffding bounds. InApproximation, ran- domization, and combinatorial optimization (Berkeley, CA, 2001), volume 2129 ofLecture Notes in Comput. Sci., pages 285–296. Springer, Berlin, 2001

    work page 2001

  23. [23]

    Perfect matchings inϵ-regular graphs and the blow-up lemma

    Vojtech Rödl and Andrzej Ruciński. Perfect matchings inϵ-regular graphs and the blow-up lemma. Combinatorica, 19(3):437–452, 1999. 16

    work page 1999

  24. [24]

    Smith, Petter E

    Barry F. Smith, Petter E. Bjørstad, and William D. Gropp.Domain decomposition. Cambridge Univer- sity Press, Cambridge, 1996. Parallel multilevel methods for elliptic partial differential equations

    work page 1996

  25. [25]

    Perfect graphs and an application to optimizing municipal services.SIAM Rev., 15:585– 590, 1973

    Alan Tucker. Perfect graphs and an application to optimizing municipal services.SIAM Rev., 15:585– 590, 1973

    work page 1973

  26. [26]

    Equitable list coloring of graphs.Taiwanese J

    Wei-Fan Wang and Ko-Wei Lih. Equitable list coloring of graphs.Taiwanese J. Math., 8(4):747–759, 2004

    work page 2004

  27. [27]

    The equitable∆-colouring conjecture holds for outerplanar graphs.Bull

    Hian Poh Yap and Yi Zhang. The equitable∆-colouring conjecture holds for outerplanar graphs.Bull. Inst. Math. Acad. Sinica, 25(2):143–149, 1997

    work page 1997

  28. [28]

    Equitable colorings of planar graphs.J

    Yi Zhang and Hian-Poh Yap. Equitable colorings of planar graphs.J. Combin. Math. Combin. Comput., 27:97–105, 1998. Arizona State University,Tempe, AZ, USA Email address:kierstead@asu.edu University of Illinois at Urbana–Champaign, Urbana, IL 61801 Email address:kostochk@illinois.edu University of Illinois at Urbana–Champaign, Urbana, IL 61801 Email addres...

    work page 1998