Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.09320 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918492984311808 |
|---|---|
| author | Barman, Siddharth Viswanathan, Vignesh |
| author_facet | Barman, Siddharth Viswanathan, Vignesh |
| contents | We study a generalization of the classical Hajnal-Szemerédi theorem to vertex-weighted graphs. Given a graph with nonnegative vertex weights, a coloring is called $α$-approximately equitable up to one vertex ($α$-EQ1) if, for each color class, the total weight remaining after removing its maximum-weight vertex is at most $α\geq 1$ times the weight of any other color class.
For vertex-weighted graphs with maximum degree $Δ$, we show that there exist instances for which no $k$-coloring is $α$-EQ1 for any $k < \frac{3Δ}{2}$ and $α< \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 $Δ$: (1) for any $\varepsilon \in (0,1)$ and all $k \geq (\frac{c}{\varepsilon^2}\ln{\frac{1}{\varepsilon}}) Δ$, there exists a $(1 + \varepsilon)$-EQ1 $k$-coloring of $G$, where $c$ is a fixed constant; and (2) for all $k \ge Δ+ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_09320 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Equitable Colorings of Vertex-Weighted Graphs Barman, Siddharth Viswanathan, Vignesh Data Structures and Algorithms Computer Science and Game Theory We study a generalization of the classical Hajnal-Szemerédi theorem to vertex-weighted graphs. Given a graph with nonnegative vertex weights, a coloring is called $α$-approximately equitable up to one vertex ($α$-EQ1) if, for each color class, the total weight remaining after removing its maximum-weight vertex is at most $α\geq 1$ times the weight of any other color class. For vertex-weighted graphs with maximum degree $Δ$, we show that there exist instances for which no $k$-coloring is $α$-EQ1 for any $k < \frac{3Δ}{2}$ and $α< \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 $Δ$: (1) for any $\varepsilon \in (0,1)$ and all $k \geq (\frac{c}{\varepsilon^2}\ln{\frac{1}{\varepsilon}}) Δ$, there exists a $(1 + \varepsilon)$-EQ1 $k$-coloring of $G$, where $c$ is a fixed constant; and (2) for all $k \ge Δ+ 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. |
| title | Equitable Colorings of Vertex-Weighted Graphs |
| topic | Data Structures and Algorithms Computer Science and Game Theory |
| url | https://arxiv.org/abs/2605.09320 |