Premium
Fractional chromatic number of a random subgraph
Author(s) -
Mohar Bojan,
Wu Hehui
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22571
Subject(s) - chromatic scale , combinatorics , mathematics , random graph , graph , discrete mathematics , critical graph , induced subgraph isomorphism problem , induced subgraph , windmill graph , line graph , graph power , vertex (graph theory) , voltage graph
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.