Fractional chromatic number of a random subgraph. Issue 3 (22nd April 2020)

• Record Type: Journal Article
• Authors: Mohar, Bojan; Wu, Hehui
• Is Part Of: Journal of graph theory. Volume 95:Issue 3(2020)
• Page Start: 467
• Page End: 472
• Publication Date: 2020-04-22
• Subjects: chromatic number -- fractional chromatic number -- Kneser graph -- random subgraph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22571
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: It is well known that a random subgraph of the complete graph K n has chromatic number Θ ( 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 ( 4 n ) ) with probability more than 1 − 1 2 n . This gives the affirmative answer for a strengthening of Bukh's question for the fractional chromatic number.