The chromatic number of random lifts of

DOI10.1016/j.endm.2009.11.051zbMath1268.05073OpenAlexW1564254624MaRDI QIDQ2840555

Babak Farzad, Dirk Oliver Theis

Publication date: 19 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2009.11.051

zbMATH Keywords

graph theoryrandom graphschromatic numbercoloringrandom lifts of graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Unnamed Item
• Random graph coverings. I: General theory and graph connectivity
• Lifts, discrepancy and nearly optimal spectral gap
• Random lifts of graphs: perfect matchings
• Minors in lifts of graphs
• Random lifts of graphs: Independence and chromatic number
• Random Lifts of Graphs: Edge Expansion
• Hamilton cycles in random lifts of graphs