Graph colorings, spaces of edges and spaces of circuits

DOI10.1016/J.AIM.2009.03.006MaRDI QIDQ1028347zbMATH OpenOpenAlexFDO

Authors Carsten A. Schultz

Publication date 30 June 2009

Published in Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph colouringgraph complexgraph homomorphism

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Relations of low-dimensional topology with graph theory (57M15)

Abstract: By Lovasz' proof of the Kneser conjecture, the chromatic number of a graph G is bounded from below by the index of the Z_2-space Hom(K_2,G) plus two. We show that the cohomological index of Hom(K_2,G) is also greater than the cohomological index of the Z_2-space Hom(C_{2r+1}, G) for r>0. This gives a new and simple proof of the strong form of the graph colouring theorem by Babson and Kozlov, which had been conjectured by Lovasz, and at the same time shows that it never gives a stronger bound than can be obtained by Hom(K_2, G). The proof extends ideas introduced by Zivaljevic in a previous elegant proof of a special case. We then generalise the arguments and obtain conditions under which corresponding results hold for other graphs in place of C_{2r+1}. This enables us to find an infinite family of test graphs of chromatic number 4 among the Kneser graphs. Our main new result is a description of the Z_2-homotopy type of the direct limit of the system of all the spaces Hom(C_{2r+1}, G) in terms of the Z_2-homotopy type of Hom(K_2, G). A corollary is that the coindex of Hom(K_2, G) does not exceed the coindex of Hom(C_{2r+1}, G) by more then one if r is chosen sufficiently large. Thus the graph colouring bound in the theorem by Babson & Kozlov is also never weaker than that from Lovasz' proof of the Kneser conjecture.

Review text

By \textit{L. Lovasz}' proof of the Kneser conjecture [J. Comb. Theory, Ser. A 25, 319--324 (1978; Zbl 0418.05028)], the chromatic number of a graph \(\Gamma\) is bounded from below by the index of the \(\mathbb Z_n\)-space \(\Hom(K_2,\Gamma)\) plus two, where \(K_2\) denotes the complete graph on two vertices. The author shows that the cohomological index of \(\Hom(K_2,\Gamma)\) is also greater than the cohomological index of the \(\mathbb Z_2\)-space \(\Hom(C_{2r+1},\Gamma)\) for \(r \geq 1\), where \(C_{2r+1}\) denotes the circuit of length \(2r+1\). This gives a new proof of the strong form of the graph colouring theorem by \textit{E. Babson} and \textit{D. N. Kozlov} [Ann. Math. (2) 165, No. 3, 965--1007 (2007; Zbl 1132.05019)] and at the same time shows that it never gives a stronger bound than can be obtained by \(\Hom(K_2,\Gamma)\). The proof given by the author was inspired by work by \textit{R. T. Zivaljevic} [Discrete Comput. Geom. 41, No. 1, 135--161 (2009; Zbl 1232.05242)]. These results are consequences of the main result of the article under review, which is a description of the \(\mathbb Z_2\)-homotopy type of the direct limit of the system of all spaces \(\Hom(C_{2r+1},\Gamma)\) in terms of the \(\mathbb Z_2\)-homotopy type of \(\Hom(K_2,\Gamma)\); cf.\ Theorems 1.5 and 6.6.

Recommendations

• Topological lower bounds for the chromatic number: a hierarchy
• Proof of the Lovász conjecture
• 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
• Complexes of graph homomorphisms
• Topological obstructions to graph colorings

Cites work

• A counterexample to a conjecture of Björner and Lovász on the \(\chi\)-coloring complex
• Canonical homeomorphisms of posets
• Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
• Cohomology of colorings of cycles
• Combinatorial groupoids, cubical complexes, and the Lovász Conjecture
• Complexes of graph homomorphisms
• Graph coloring manifolds
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• scientific article; zbMATH DE number 3390006 (Why is no real title available?)
• Kneser's conjecture, chromatic number, and homotopy
• On the Kunneth Formula and Functorial Dependence in Algebraic Topology
• Proof of the Lovász conjecture
• 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
• Topology of Hom complexes and test graphs for bounding chromatic number
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler

Cited in

(21)

• Homotopy groups of Hom complexes of graphs
• A topological lower bound for the chromatic number of a special family of graphs
• Topology of Hom complexes and test graphs for bounding chromatic number
• Homomorphism complexes and maximal chains in graded posets
• \(\mathbb{Z}_2\)-indices and Hedetniemi's conjecture
• Knight move in chromatic cohomology
• Homomorphism complexes, reconfiguration, and homotopy for directed graphs
• scientific article; zbMATH DE number 3855142 (Why is no real title available?)
• Cohomology of colorings of cycles
• Stiefel manifolds and coloring the pentagon
• On pallets for Fox colorings of spatial graphs
• Answers to some problems about graph coloring test graphs
• Paths of homomorphisms from stable Kneser graphs
• Hedetniemi's conjecture and strongly multiplicative graphs
• Hom complexes and homotopy in the category of graphs
• Deformation retracts of neighborhood complexes of stable Kneser graphs
• The equivariant topology of stable Kneser graphs
• Hom complexes of graphs whose codomains are square-free
• Box complexes: at the crossroad of graph theory and topology
• Set partition complexes
• On the topological lower bound for the multichromatic number

This page was built for publication: Graph colorings, spaces of edges and spaces of circuits

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