Random Lifts of $K_5\backslashe$ are 3-Colorable

DOI10.1137/110838078zbMath1245.05114arXiv1003.1527MaRDI QIDQ2902895

Dirk Oliver Theis, Babak Farzad

Publication date: 22 August 2012

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1003.1527

zbMATH Keywords

graph theory; random graphs; chromatic number; coloring; random lifts of graphs

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

05C15: Coloring of graphs and hypergraphs

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)