pith. machine review for the scientific record. sign in

arxiv: 2605.09320 · v1 · submitted 2026-05-10 · 💻 cs.DS · cs.GT

Recognition: 2 theorem links

· Lean Theorem

Equitable Colorings of Vertex-Weighted Graphs

Siddharth Barman , Vignesh Viswanathan
Authors on Pith no claims yet

Pith reviewed 2026-05-12 02:36 UTC · model grok-4.3

classification 💻 cs.DS cs.GT
keywords equitable coloringvertex-weighted graphapproximate equitabilityHajnal-Szemerédi theoremfair divisiongraph coloringmaximum degreepolynomial-time algorithm
0
0 comments X

The pith

Vertex-weighted graphs with maximum degree Δ admit (1+ε)-equitable k-colorings for k at least (c/ε² log(1/ε))Δ and 2-equitable ones for any k at least Δ+1.

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

The paper extends the classical Hajnal-Szemerédi theorem on equitable colorings to graphs in which vertices carry nonnegative weights. It introduces α-EQ1 colorings, where for each color class the total weight after removing its single heaviest vertex is at most α times the weight of any other class. The main theorems establish that for every small ε a (1+ε)-EQ1 coloring exists once the number of colors reaches a modest multiple of Δ, and that a 2-EQ1 coloring exists already at Δ+1 colors; both are computable in polynomial time. A reader cares because the results supply concrete fairness guarantees when partitioning weighted objects subject to pairwise incompatibility constraints encoded by the graph.

Core claim

For any vertex-weighted graph G with maximum degree Δ the authors prove two existence statements. For every ε in (0,1) and every k at least (c/ε² ln(1/ε))Δ there exists a (1+ε)-EQ1 k-coloring of G. For every k at least Δ+1 there exists a 2-EQ1 k-coloring of G. Both colorings can be found by polynomial-time algorithms. They also exhibit graphs showing that no α-EQ1 coloring is possible for k smaller than 3Δ/2 when α is smaller than √2.

What carries the argument

The α-EQ1 coloring condition, which requires that after discarding the single maximum-weight vertex from each color class the remaining class weights differ by a multiplicative factor of at most α.

If this is right

  • The colorings supply fairness guarantees in constrained fair-division problems where items have weights and conflicts are modeled by edges.
  • They yield concentration inequalities that apply to families of partly dependent random variables.
  • Polynomial-time algorithms become available for computing the colorings.
  • The work also supplies sufficient conditions for the existence of k-colorings that are equitable with respect to any prescribed partition of the vertex set.

Where Pith is reading between the lines

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

  • The same degree-linear bounds may carry over to other notions of approximate balance, such as those based on variance or entropy rather than worst-case vertex removal.
  • The partition-equitability conditions derived en route could be reused in load-balancing or scheduling problems on conflict graphs.
  • Whether the logarithmic factor in the bound on k can be removed or improved remains open and would be a natural target for tighter analysis.

Load-bearing premise

The results depend on the α-EQ1 definition being an acceptable relaxation of weight equality and on every input graph having a finite, well-defined maximum degree Δ.

What would settle it

A concrete vertex-weighted graph with maximum degree Δ for which no (1+ε)-EQ1 coloring exists even when k greatly exceeds (c/ε² ln(1/ε))Δ would disprove the first positive claim.

read the original abstract

We study a generalization of the classical Hajnal-Szemer\'edi theorem to vertex-weighted graphs. Given a graph with nonnegative vertex weights, a coloring is called $\alpha$-approximately equitable up to one vertex ($\alpha$-EQ1) if, for each color class, the total weight remaining after removing its maximum-weight vertex is at most $\alpha \geq 1$ times the weight of any other color class. For vertex-weighted graphs with maximum degree $\Delta$, we show that there exist instances for which no $k$-coloring is $\alpha$-EQ1 for any $k < \frac{3\Delta}{2}$ and $\alpha < \sqrt{2}$. In light of this impossibility, we relax these parameters and establish the following results for any vertex-weighted graph $G$ with maximum degree $\Delta$: (1) for any $\varepsilon \in (0,1)$ and all $k \geq (\frac{c}{\varepsilon^2}\ln{\frac{1}{\varepsilon}}) \Delta$, there exists a $(1 + \varepsilon)$-EQ1 $k$-coloring of $G$, where $c$ is a fixed constant; and (2) for all $k \ge \Delta + 1$, there exists a $2$-EQ1 $k$-coloring of $G$. Furthermore, such equitable colorings can be computed in polynomial time. En route to our results on equitability under vertex weights, we establish sufficient conditions for the existence of $k$-colorings that are equitable with respect to any given partition of the vertex set. Our coloring results correspond to fairness guarantees in a constrained fair division setting and lead to concentration inequalities for partly dependent random variables.

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 / 2 minor

Summary. The paper generalizes the Hajnal-Szemerédi theorem to vertex-weighted graphs. It introduces the notion of an α-EQ1 k-coloring, in which each color class, after deletion of its heaviest vertex, has total weight at most α times the weight of any other class. For any graph of maximum degree Δ the authors prove an impossibility result (no α-EQ1 coloring exists for k < 3Δ/2 and α < √2) and two positive results: (i) for every ε ∈ (0,1) there exists a (1+ε)-EQ1 k-coloring whenever k ≥ (c/ε² ln(1/ε))Δ, and (ii) a 2-EQ1 k-coloring exists for every k ≥ Δ+1. Both families of colorings are computable in polynomial time. As an intermediate step the authors give sufficient conditions for the existence of k-colorings that are equitable with respect to an arbitrary prescribed partition of the vertex set; the results are also interpreted as fairness guarantees in constrained fair division and as concentration bounds for partly dependent random variables.

Significance. If the proofs are correct, the work supplies the first non-trivial weighted analogue of the Hajnal-Szemerédi theorem together with explicit polynomial-time algorithms. The intermediate partition-equitable coloring lemma and the explicit dependence on Δ and ε are technically useful; the links to fair division and to concentration inequalities for dependent variables broaden the potential impact beyond pure graph theory.

major comments (1)
  1. [Main algorithmic theorems (Section 4)] The polynomial-time claim for both families of colorings is stated in the abstract and in the main theorems, yet the manuscript does not indicate whether the algorithms rely on the constructive version of Hajnal-Szemerédi or on a separate probabilistic-method-plus-derandomization argument. Because the central algorithmic contribution rests on this point, an explicit reference to the derandomization technique (or to the section containing the running-time analysis) is required.
minor comments (2)
  1. [Theorem 1.2] The constant c appearing in the bound k ≥ (c/ε² ln(1/ε))Δ is left unspecified. An explicit numerical upper bound on c (or a short derivation showing how it arises from the Lovász Local Lemma or similar tool) would make the result more concrete.
  2. [Definition 1.1] In the definition of α-EQ1 coloring the phrase “at most α times the weight of any other color class” should be clarified to state whether the comparison is with the total weight of the other class or with the weight after its own heaviest vertex is removed; the current wording admits both readings.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading, the positive assessment of the work, and the recommendation for minor revision. The single major comment identifies a point of clarity regarding our algorithmic claims; we agree that an explicit reference is warranted and will incorporate the requested clarification in the revised manuscript.

read point-by-point responses

  1. Referee: [Main algorithmic theorems (Section 4)] The polynomial-time claim for both families of colorings is stated in the abstract and in the main theorems, yet the manuscript does not indicate whether the algorithms rely on the constructive version of Hajnal-Szemerédi or on a separate probabilistic-method-plus-derandomization argument. Because the central algorithmic contribution rests on this point, an explicit reference to the derandomization technique (or to the section containing the running-time analysis) is required.

    Authors: We agree that the algorithmic basis for the polynomial-time claims should be stated explicitly. The (1+ε)-EQ1 colorings are obtained via a probabilistic-method argument that is derandomized using the method of conditional expectations; the full running-time analysis appears in Section 4.2. The 2-EQ1 colorings are computed constructively by building on the known algorithmic version of the Hajnal-Szemerédi theorem, with the extension and implementation details given in Sections 3 and 4.1. We will add a short clarifying paragraph at the start of Section 4 (and a corresponding sentence in the statements of the main theorems) that directly references these sections and the derandomization technique employed. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation relies on the classical Hajnal-Szemerédi theorem for the unweighted case, combined with new sufficient conditions for partition-equitable colorings and standard algorithmic techniques for polynomial-time computation. The impossibility threshold and the relaxed positive results (larger k or α=2) are derived from these without any equation or parameter reducing by construction to a fitted input, self-definition, or self-citation chain. No load-bearing step renames a known result or imports uniqueness via the authors' prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the classical Hajnal-Szemerédi theorem for the unweighted case and on standard techniques from graph coloring and approximation algorithms; no free parameters are fitted to data and no new entities are postulated.

axioms (1)
  • domain assumption Hajnal-Szemerédi theorem: every graph with maximum degree Δ is (Δ+1)-colorable with equitable color classes
    Invoked as the base case that the paper generalizes to weighted vertices.

pith-pipeline@v0.9.0 · 5613 in / 1416 out tokens · 54483 ms · 2026-05-12T02:36:56.633897+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    Proof of a conjecture of

    Hajnal, Andr. Proof of a conjecture of. Combinatorial Theory and its Applications , year =

    work page

  2. [2]

    Advances in Mathematics , volume=

    Splitting necklaces , author=. Advances in Mathematics , volume=. 1987 , publisher=

    work page 1987

  3. [3]

    Barman, Siddharth and Khan, Arindam and Shyam, Sudarshan and Sreenivas, K. V. N. , title =. 2023 , booktitle = proc #

    work page 2023

  4. [4]

    2008 , booktitle = proc #

    Pemmaraju, Sriram and Srinivasan, Aravind , title =. 2008 , booktitle = proc #

    work page 2008

  5. [5]

    2005 , publisher =

    Probability and Computing: Randomized Algorithms and Probabilistic Analysis , author =. 2005 , publisher =

    work page 2005

  6. [6]

    T\^ohoku Mathematical Journal , volume =

    Azuma, Kazuoki , title =. T\^ohoku Mathematical Journal , volume =

    work page

  7. [7]

    Mathematical Proceedings of the Cambridge Philosophical Society , volume =

    On colouring the nodes of a network , author =. Mathematical Proceedings of the Cambridge Philosophical Society , volume =. 1941 , publisher =

    work page 1941

  8. [8]

    Autonomous Agents and Multi-Agent Systems , volume =

    Hummel, Halvard and Hetland, Magnus Lie , title =. Autonomous Agents and Multi-Agent Systems , volume =

    work page

  9. [9]

    Random Structures & Algorithms , volume =

    Janson, Svante , title =. Random Structures & Algorithms , volume =

    work page

  10. [10]

    , booktitle =

    Pemmaraju, Sriram V. , booktitle =. Equitable Coloring Extends

    work page

  11. [11]

    Journal of the American Statistical Association , volume =

    Probability Inequalities for Sums of Bounded Random Variables , author =. Journal of the American Statistical Association , volume =. 1963 , publisher =

    work page 1963

  12. [12]

    Aiya Kuchukova and Will Perkins and Xavier Povill , title =

    work page

  13. [13]

    Kierstead, H. A. and Kostochka, A. V. , title =. Combinatorics, Probability and Computing , volume =. 2008 , publisher =

    work page 2008

  14. [14]

    Fair Packing of Independent Sets , year =

    Chiarelli, Nina and Krnc, Matja. Fair Packing of Independent Sets , year =. Combinatorial Algorithms: 31st International Workshop (IWOCA 2020) , pages =

    work page 2020

  15. [15]

    On the computability of equitable divisions , volume =

    Katar. On the computability of equitable divisions , volume =. Discrete Optimization , keywords =

    work page

  16. [16]

    L. E. Dubins and E. H. Spanier , journal =. How to Cut A Cake Fairly , volume =

    work page

  17. [17]

    Equitable Allocations of Indivisible Goods , year =

    Freeman, Rupert and Sikdar, Sujoy and Vaish, Rohit and Xia, Lirong , booktitle = proc #. Equitable Allocations of Indivisible Goods , year =

    work page

  18. [18]

    Near fairness in matroids , year =

    Gourv\`. Near fairness in matroids , year =

    work page

  19. [19]

    Journal of Artificial Intelligence Research , numpages =

    Barman, Siddharth and Bhaskar, Umang and Pandit, Yeshwant and Pyne, Soumyajit , title =. Journal of Artificial Intelligence Research , numpages =. 2026 , volume =

    work page 2026