Back to Search
Start Over
Fractional chromatic number of a random subgraph
- Publication Year :
- 2018
-
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.<br />Comment: Short note
- Subjects :
- Mathematics - Combinatorics
05C15, 05C80
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1807.06285
- Document Type :
- Working Paper