Fractional coloring via entropy
In recent work, Martinsson and Steiner proved that triangle-free $d$-degenerate graphs have fractional chromatic number $χ_f(G) = O\left(\frac{d}{\log d}\right)$. Here, we introduce an alternate proof of the bound rooted in the analysis of the entropy of certain random variables. Beyond simplifying the original argument, our technique naturally generalizes to broader settings. In this paper, we focus on two extensions of the result. First, we consider locally $r$-colorable graphs $G$, where $χ(G[N(v)]) \le r$ for every vertex $v$. We show that $d$-degenerate locally $r$-colorable graphs…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.17730
curl -X POST /api/v1/records/arxiv/2603.17730/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.17730/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'