On Fair and Tolerant Colorings of Graphs
Saeed Shaebani · 2025
Read On Fair and Tolerant Colorings of Graphs by Saeed Shaebani (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-14871.txt.
Description
Saeed Shaebani studies a relaxed kind of graph coloring in which the color classes need not follow the usual rules. In a fair and tolerant coloring, each vertex must see the same share of neighbors in its own color and in every other color. The largest number of colors for which this is possible is called the FAT chromatic number.
Shaebani takes up a question left open by the researchers who introduced the idea, who asked whether a bound links this number to the degrees of the vertices. The paper gives conditions under which such colorings exist and studies how the number behaves. It adds a new tool for splitting networks into balanced groups.
Catalog record
| CREATOR | Saeed Shaebani |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-14871