Random lifts of graphs: Independence and chromatic number
From MaRDI portal
Publication:4534214
DOI10.1002/rsa.10003zbMath0993.05071MaRDI 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
05C15: Coloring of graphs and hypergraphs
Related Items
On the Number of Perfect Matchings in Random Lifts, Hamilton cycles in random lifts of graphs, Hamilton cycles in random lifts of graphs, Equitable partition for some Ramanujan graphs, Expansion of random graphs: new proofs, new results, Relative expanders or weakly relatively Ramanujan graphs., Random lifts of graphs are highly connected, The spectral norm of random lifts of matrices, Cutoff for random lifts of weighted graphs, \(L^p\) norms and support of eigenfunctions on graphs, Interlacing families. I: Bipartite Ramanujan graphs of all degrees, Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number, The chromatic numbers of double coverings of a graph, The chromatic number of random lifts of, Tight products and graph expansion, Word maps and spectra of random graph lifts, Expander graphs and their applications
Cites Work