pith. sign in

arxiv: 1807.06285 · v1 · pith:JP7UYA7Knew · submitted 2018-07-17 · 🧮 math.CO

Fractional chromatic number of a random subgraph

classification 🧮 math.CO
keywords chromaticnumberfractionalrandomsubgraphgraphleastbukh
0
0 comments X
read the original abstract

It is well known that a random subgraph of the complete graph $K_n$ has chromatic number $\Theta(n/\log n)$ w.h.p. Boris Bukh asked whether the same holds for a random subgraph of any $n$-chromatic graph, at least in expectation. In this paper it is shown that for every graph, whose fractional chromatic number is at least $n$, the fractional chromatic number of its random subgraph is at least $n/(8\log_2(4n))$ with probability more than $1-\frac{1}{2n}$. This gives the affirmative answer for a strengthening of Bukh's question for the fractional chromatic number.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.