Random lifts of K₅e are 3-colorable

DOI10.1137/110838078zbMATH Open1245.05114arXiv1003.1527OpenAlexW2026925081MaRDI QIDQ2902895FDOQ2902895

Authors: Babak Farzad, Dirk Oliver Theis 

Publication date: 22 August 2012

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

Abstract: Amit, Linial, and Matouvsek (Random lifts of graphs III: independence and chromatic number, Random Struct. Algorithms, 2001) have raised the following question: Is the chromatic number of random $h$-lifts of $K_5$ asymptotically (for $hoinfty$) almost surely equal to a single number? In this paper, we offer the following partial result: The chromatic number of a random lift of $K_{5}setminuse$ is asymptotically almost surely three.

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

Recommendations

• The chromatic number of random lifts of \(K_5\setminus e\)
• Random lifts of graphs: Independence and chromatic number
• On the chromatic number of a random 5-regular graph
• Minors in lifts of graphs
• Random lifts of graphs

zbMATH Keywords

graph theorychromatic numberrandom graphscoloringrandom lifts of graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Coloring of graphs and hypergraphs (05C15)

Cited In (2)

• Random lifts of graphs: Independence and chromatic number
• The chromatic number of random lifts of \(K_5\setminus e\)

This page was built for publication: Random lifts of \({K_5}\setminus{e}\) are 3-colorable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2902895)