Minors in lifts of graphs

DOI10.1002/RSA.20100MaRDI QIDQ3419590zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Yotam Drier, Nathan Linial

Publication date 7 February 2007

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20100

zbMATH Keywords

Hadwiger numberHajós numberliftsrandom lifts

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph minors (05C83)

Recommendations

• Random lifts of graphs
• Hamilton cycles in random lifts of graphs
• Random lifts of graphs: Independence and chromatic number
• Random lifts of graphs are highly connected
• The chromatic number of random lifts of \(K_5\setminus e\)

Cites work

• Hadwiger's conjecture is true for almost every graph
• Random lifts of graphs
• Topological cliques in graphs II

Cited in

(13)

• Random lifts of graphs are highly connected
• On the number of forests and connected spanning subgraphs
• Cutoff for random lifts of weighted graphs
• Upper bound for the number of spanning forests of regular graphs
• Random lifts of graphs
• The chromatic number of random lifts of \(K_5\setminus e\)
• Random lifts of \({K_5}\setminus{e}\) are 3-colorable
• Expander graphs and their applications
• Low-distortion embeddings of graphs with large girth
• Random lifts of graphs: Independence and chromatic number
• Complete Minors in Graphs Without Sparse Cuts
• \(\delta\)-connectivity in random lifts of graphs
• Minors in small-set expanders

This page was built for publication: Minors in lifts of graphs

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