Box complexes, neighborhood complexes, and the chromatic number
Copyright policy )Box complexes, neighborhood complexes, and the chromatic number
Lovasz'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.
8 pages, 1 figure
- Institute of Theoretical Computer Science Switzerland
- Technical University of Berlin Germany
- Technical University of Berlin Germany
- ETH Zurich Switzerland
- Technical University Eindhoven Netherlands
Hypergraphs, Theoretical Computer Science, box complexes, Kneser conjecture, Coloring of graphs and hypergraphs, 05C15, Computational Theory and Mathematics, 55P10, 57M15, graph coloring, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Algebraic Topology (math.AT), Relations with graph theory, Mathematics - Algebraic Topology, Combinatorics (math.CO), Homotopy equivalences in algebraic topology, Relations of low-dimensional topology with graph theory, Homotopy equivalences, 05C15; 55P10; 57M15
Hypergraphs, Theoretical Computer Science, box complexes, Kneser conjecture, Coloring of graphs and hypergraphs, 05C15, Computational Theory and Mathematics, 55P10, 57M15, graph coloring, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Algebraic Topology (math.AT), Relations with graph theory, Mathematics - Algebraic Topology, Combinatorics (math.CO), Homotopy equivalences in algebraic topology, Relations of low-dimensional topology with graph theory, Homotopy equivalences, 05C15; 55P10; 57M15
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).24 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!