Random lifts of graphs: Independence and chromatic number
Authors:
- 3 December 2001
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 20 (1) , 1-22
Abstract
For a graph G, a random n‐lift of G has the vertex set V(G)×[n] and for each edge [u, v] ∈ E(G), there is a random matching between {u}×[n] and {v}×[n]. We present bounds on the chromatic number and on the independence number of typical random lifts, with G fixed and n→∞. For the independence number, upper and lower bounds are obtained as solutions to certain optimization problems on the base graph. For a base graph G with chromatic number χ and fractional chromatic number χf, we show that the chromatic number of typical lifts is bounded from below by const ⋅ \documentclass{article}\pagestyle{empty}$\sqrt{\chi/\log\chi}$ and also by const ⋅ χf/log2χf (trivially, it is bounded by χ from above). We have examples of graphs where the chromatic number of the lift equals χ almost surely, and others where it is a.s. O(χ/logχ). Many interesting problems remain open. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 1–22, 2002Keywords
This publication has 7 references indexed in Scilit:
- A Graph with cover degeneracy less than chromatic numberJournal of Graph Theory, 2001
- Models of Random Regular Graphs1999
- On Brooks' Theorem for Sparse GraphsCombinatorics, Probability and Computing, 1995
- Graph Coloring Problems1994
- A generalized van Kampen-Flores theoremProceedings of the American Mathematical Society, 1991
- A generalized kneser conjectureJournal of Combinatorial Theory, Series B, 1990
- The chromatic number of random graphsCombinatorica, 1988