Random lifts of K₅e are 3-colorable

DOI10.1137/110838078MaRDI QIDQ2902895zbMATH OpenOpenAlexFDO

Authors Babak Farzad, Dirk Oliver Theis

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 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)

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.

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

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)