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

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