Fractional colorings of K_r-free graphs with local demands

Abstract

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)≤ c_r(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 (loglog d(v))². In this paper, we prove their conjecture, showing that ϕ(v)≤c/r(log(d(v)+2))/(d(v)+1) suffices for an absolute constant c>0. As a corollary, we obtain a lower bound on the independence number of K_r-free graphs in terms of their degree sequence. This strengthens the bound that OpenAI proved in resolving the Ajtai-Erdős-Komlós-Szemerédi conjecture. Moreover, our argument yields a deterministic algorithm that produces the desired probability distribution in time 2^O(r²)n^O(1), where n is the number of vertices and the implied constants are absolute.

Weighted odd-cycle transversals and fractional colorings of planar graphs
Xiaolan Hu, Jiaao Li, Zhouningxin Wang
arXiv22 Oct 2026PreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
Optimal K_t-free list colorings and the Pollyanna property of graphs with no triangular wheel
Hongyang Wang, Rong Wu
arXiv26 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Fractional DP-colorings of d-degenerate locally sparse graphs
Abhishek Dhawan, Huy Nguyen, Rohan A. Rathi
arXiv11 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Cayley graphs of abelian groups, circular colorings and discrete fundamental groups
Kengo Enami, Takahiro Matsushita
arXiv26 Oct 2026PreprintarXiv licenceFull textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
Mohammed Lalou, Nader Mbarek, Abdallah Skender +1
arXiv6 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{davies2026fractional,
  title = {{Fractional colorings of $K_r$-free graphs with local demands}},
  author = {Ewan Davies and Abhishek Dhawan and Abhishek Methuku and Huy Nguyen and Jaehyeon Seo},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.04297},
  eprint = {2611.04297},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.04297},
}

RIS

TY  - UNPB
TI  - Fractional colorings of K_r-free graphs with local demands
AU  - Ewan Davies
AU  - Abhishek Dhawan
AU  - Abhishek Methuku
AU  - Huy Nguyen
AU  - Jaehyeon Seo
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.04297
UR  - https://arxiv.org/abs/2611.04297
AB  - 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)≤ c_r(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 (loglog d(v))^2. In this paper, we prove their conjecture, showing that ϕ(v)≤c/r(log(d(v)+2))/(d(v)+1) suffices for an absolute constant c>0. As a corollary, we obtain a lower bound on the independence number of K_r-free graphs in terms of their degree sequence. This strengthens the bound that OpenAI proved in resolving the Ajtai-Erdős-Komlós-Szemerédi conjecture. Moreover, our argument yields a deterministic algorithm that produces the desired probability distribution in time 2^O(r^2)n^O(1), where n is the number of vertices and the implied constants are absolute.
ER  -

Abstract

Related

Cite