Fractional colorings of $K_r$-free graphs with local demands

Source: arxiv.org/abs/2611.04297

Ewan Davies, Abhishek Dhawan, Abhishek Methuku, Huy Nguyen, Jaehyeon Seo

arXivarxiv/2611.04297Nov 3, 2026math.COscore 0

We study fractional coloring with local demands, a framework introduced by Kelly and Postle in which one seeks a probability distribution on the independent sets of a graph such that each vertex $v$ is included with probability at least a prescribed target $φ(v)$. For $K_r$-free graphs, Kelly and Postle conjectured that such a distribution exists provided $φ(v)\le c_r\frac{\log d(v)}{d(v)}$ for a fixed \(c_r>0\), where $d(v)$ is the degree of $v$, and they established this up to a factor of $(\log\log d(v))^2$. In this paper, we prove their conjecture, showing that \[…

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2611.04297
curl -X POST /api/v1/records/arxiv/2611.04297/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.04297/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'