Box complexes, neighborhood complexes, and the chromatic number

Simple item page
dc.creatorCsorba, Peter
dc.creatorLange, Carsten
dc.creatorSchurr, Ingo
dc.creatorWassmer, Arnold
dc.date2003-10-21
dc.date.accessioned2026-07-07T05:02:09Z
dc.date.available2026-07-07T05:02:09Z
dc.descriptionLovasz's striking proof of Kneser's conjecture from 1978 using the Borsuk--Ulam theorem provides a lower bound on the chromatic number of a graph. We introduce the shore subdivision of simplicial complexes and use it to show an upper bound to this topological lower bound and to construct a strong Z_2-deformation retraction from the box complex (in the version introduced by Matousek and Ziegler) to the Lovasz complex. In the process, we analyze and clarify the combinatorics of the complexes involved and link their structure via several ``intermediate'' complexes.
dc.description8 pages, 1 figure
dc.identifierhttps://arxiv.org/abs/math/0310339
dc.identifierhttp://arxiv.org/abs/math/0310339
dc.identifierJournal of Combinatorial Theory, Series A 108 (2004), pp. 159-168.
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/68944
dc.subjectCombinatorics
dc.subjectAlgebraic Topology
dc.subject05C15; 55P10; 57M15
dc.titleBox complexes, neighborhood complexes, and the chromatic number
dc.typetext

Files

Collections

arXiv