Random lifts of graphs: Independence and chromatic number

DOI10.1002/rsa.10003zbMath0993.05071OpenAlexW1971907125MaRDI QIDQ4534214

Alon Amit, Nathan Linial, Ji{ří} Matoušek

Publication date: 20 September 2002

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10003

zbMATH Keywords

fractional chromatic numberindependence numberrandom graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (18)

Cutoff for random lifts of weighted graphs ⋮ Tight products and graph expansion ⋮ Node and edge averaged complexities of local graph problems ⋮ Equitable partition for some Ramanujan graphs ⋮ Expander graphs and their applications ⋮ Random lifts of graphs are highly connected ⋮ Relative expanders or weakly relatively Ramanujan graphs. ⋮ Expansion of random graphs: new proofs, new results ⋮ Hamilton cycles in random lifts of graphs ⋮ On the Number of Perfect Matchings in Random Lifts ⋮ Hamilton cycles in random lifts of graphs ⋮ Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number ⋮ Word maps and spectra of random graph lifts ⋮ The chromatic numbers of double coverings of a graph ⋮ \(L^p\) norms and support of eigenfunctions on graphs ⋮ The spectral norm of random lifts of matrices ⋮ The chromatic number of random lifts of ⋮ Interlacing families. I: Bipartite Ramanujan graphs of all degrees

Cites Work

• Unnamed Item
• A generalized Kneser conjecture
• On Brooks' Theorem for Sparse Graphs
• Random Lifts of Graphs: Edge Expansion
• The chromatic number of random graphs

This page was built for publication: Random lifts of graphs: Independence and chromatic number