Topology of Hom complexes and test graphs for bounding chromatic number

DOI10.1007/S11856-011-0085-6zbMath1292.05090arXiv0907.5079OpenAlexW2037549114MaRDI QIDQ1758983

Anton Dochtermann, Carsten A. Schultz

Publication date: 19 November 2012

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

posets\(\Gamma\)-actions on graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial aspects of simplicial complexes (05E45)

Related Items (16)

Generalised Mycielski graphs, signature systems, and bounds on chromatic numbers ⋮ Warmth and edge spaces of graphs ⋮ Neighborhood complexes, homotopy test graphs and an application to coloring of product graphs ⋮ The equivariant topology of stable Kneser graphs ⋮ Homomorphism complexes, reconfiguration, and homotopy for directed graphs ⋮ Answers to some problems about graph coloring test graphs ⋮ Paths of homomorphisms from stable Kneser graphs ⋮ Deformation retracts of neighborhood complexes of stable Kneser graphs ⋮ Hedetniemi's conjecture and adjoint functors in thin categories ⋮ On topological relaxations of chromatic conjectures ⋮ Homomorphism complexes, reconfiguration, and homotopy for directed graphs ⋮ Homotopy groups of Hom complexes of graphs ⋮ Graph colorings, spaces of edges and spaces of circuits ⋮ \(\mathbb{Z}_2\)-indices and Hedetniemi's conjecture ⋮ On inverse powers of graphs and topological implications of Hedetniemi's conjecture ⋮ Homotopy types of the Hom complexes of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kneser's conjecture, chromatic number, and homotopy
• A short proof of \(w_{1}^n (\text{Hom}(C_{2r+1}, K_{n+2})) = 0\) for all \(n\) and a graph colouring theorem by Babson and Kozlov
• Local chromatic number, Ky Fan's theorem, and circular colorings
• Homotopy types of box complexes
• The universality of Hom complexes of graphs
• Hom complexes and homotopy theory in the category of graphs
• Homotopy groups of Hom complexes of graphs
• Combinatorial groupoids, cubical complexes, and the Lovász Conjecture
• Graph colorings, spaces of edges and spaces of circuits
• Group actions on posets
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Complexes of graph homomorphisms
• Proof of the Lovász conjecture
• WI-posets, graph complexes and \(\mathbb{Z}_2\)-equivalences
• A counterexample to a conjecture of Björner and Lovász on the \(\chi\)-coloring complex
• Fractional chromatic numbers of cones over graphs
• On graphs with strongly independent color-classes

This page was built for publication: Topology of Hom complexes and test graphs for bounding chromatic number