Homomorphism complexes and k-cores

DOI10.1016/J.DISC.2018.06.014zbMATH Open1392.05056arXiv1601.07854OpenAlexW2963973044MaRDI QIDQ724876FDOQ724876

Authors: Greg Malen 

Publication date: 26 July 2018

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

Abstract: We prove that the topological connectivity of a graph homomorphism complex Hom($G,K_m$) is at least $m-D(G)-2$, where $displaystyleD(G)=ma{x}_{HsubseteqG}delta(H)$. This is a strong generalization of a theorem of Cuki'{c} and Kozlov, in which $D(G)$ is replaced by the maximum degree $Delta(G)$. It also generalizes the graph theoretic bound for chromatic number, $displaystylechi(G)leqD(G)+1$, as $displaystylechi(G)=minm:extHom(G,K_m)eqvarnothing$. Furthermore, we use this result to examine homological phase transitions in the random polyhedral complexes Hom$(G(n,p),K_m)$ when $p=c/n$ for a fixed constant $c>0$.

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

Recommendations

• Complexes of graph homomorphisms
• scientific article; zbMATH DE number 2211584
• A short proof of a conjecture on the connectivity of graph coloring complexes
• scientific article
• Homology of \(\operatorname{Hom}\) complexes

zbMATH Keywords

degeneracy\(k\)-coresHom-complexesrandom polyhedral complexes

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Enumeration in graph theory (05C30) Relations of low-dimensional topology with graph theory (57M15) Homotopy equivalences in algebraic topology (55P10)

Cites Work

• Title not available (Why is that?)
• Poisson convergence and Poisson processes with applications to random graphs
• Sudden emergence of a giant \(k\)-core in a random graph
• Kneser's conjecture, chromatic number, and homotopy
• Mixing 3-colourings in bipartite graphs
• Complexes of graph homomorphisms
• Cohomology of colorings of cycles
• Title not available (Why is that?)
• On colouring random graphs
• Title not available (Why is that?)
• Small models of graph colouring manifolds and the Stiefel manifolds \(\Hom(C_{5},K_n)\)
• The homotopy type of complexes of graph homomorphisms between cycles
• The neighborhood complex of a random graph
• A short proof of a conjecture on the connectivity of graph coloring complexes
• Title not available (Why is that?)
• Between 2- and 3-colorability

Cited In (5)

• Connectedness of certain graph coloring complexes
• Homomorphism complexes, reconfiguration, and homotopy for directed graphs
• Homology of \(\operatorname{Hom}\) complexes
• Homomorphisms between graphs embedded in surfaces
• Homology of non-\(k\)-overlapping discs

This page was built for publication: Homomorphism complexes and \(k\)-cores

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