Document Type
Lecture
Publication Date
2-11-2015
Abstract
For a graph G let Gp denote the subgraph of G, in which each edge of G is in Gp with probability p independently at random. Boris Bukh asked whether there is a constant c > 0 so that E( (G1 2)) > c (G) log( (G)). Afractional chromatic number of graph G, denoted by f(G), is the minimum total weight of independent sets , such that for each vertex x, the independent sets contains x has total weight at least 1. We prove the analogous fractional chromatic number version of Boris Bukhs conjecture: there is a constant c > 0, so that E( f(G1 2)) > c f(G) log( f(G)).
Relational Format
presentation
Recommended Citation
Wu, Hehui, "Fractional Chromatic Number of Random Subgraphs" (2015). Combinatorics Seminar. 42.
https://egrove.olemiss.edu/math_combinatorics/42
