Kneser's conjecture, chromatic number, and homotopy
From MaRDI portal
The author proves a result on the simplicial complex formed by the neighborhoods of points of a graph and applies that to obtain an elegant proof of the Kneser conjecture of 1955 asserting that if the \(n\)-subsets of a \((2n+k)\)-element set is split into \(k+1\) classes, then one of the classes will contain two disjoint \(n\)-subsets. The proof depends on the theorem of \textit{K. Borsuk} [Fundam. Math. 20, 177--190 (1933; Zbl 0006.42403; JFM 59.0560.01)] that if the \(k\)-dimensional unit sphere is covered by \(k+1\) closed sets, then one of these contains two antipodal points.
Recommendations
- Chromatic homology, Khovanov homology, and torsion
- Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
- Chromatic numbers and Bohr topologies
- Chromatic numbers of simplicial manifolds
- Topology of Hom complexes and test graphs for bounding chromatic number
- Some Conjectures and Questions in Chromatic Topological Graph Theory
- The Chromatic Number of Kneser Hypergraphs
- Chromatic numbers of stable Kneser hypergraphs via topological Tverberg-type theorems
- On the chromatic number of Kneser hypergraphs
- Equivariant Cohomology and Lower Bounds for Chromatic Numbers
Cites work
Cited in
(only showing first 100 items - show all)- Hom complexes and homotopy theory in the category of graphs
- Topological obstructions for vertex numbers of Minkowski sums
- Homotopy groups of Hom complexes of graphs
- Coloring the square of the Kneser graph \(\mathrm{KG}(2k+1,k)\) and the Schrijver graph \(\mathrm{SG}(2k+2,k)\)
- Combinatorial groupoids, cubical complexes, and the Lovász Conjecture
- Colorful flowers
- Large disjoint subgraphs with the same order and size
- Vizing's conjecture for chordal graphs
- Graph colorings, spaces of edges and spaces of circuits
- On colorings of graph powers
- On \(b\)-coloring of the Kneser graphs
- A generalization of the Erdős-Ko-Rado theorem
- Extremal problems concerning Kneser-graphs
- Hamiltonian uniform subset graphs
- Large independent sets in shift-invariant graphs
- A class of additive multiplicative graph functions
- The chromatic connectivity of graphs
- The complexity of multicolouring
- Maximum bipartite subgraphs of Kneser graphs
- On constructive methods in the theory of colour-critical graphs
- On locally-perfect colorings
- A certain combinatorial inequality
- A combinatorial proof of the Borsuk-Ulam antipodal point theorem
- A note on induced cycles in Kneser graphs
- The colored Tverberg's problem and complexes of injective functions
- A generalization of the ham sandwich theorem
- Helly property in finite set systems
- A short proof of Kneser's conjecture
- Long induced paths and cycles in Kneser graphs
- The algebra of flows in graphs
- Colorations généralisées, graphes biorientés et deux ou trois choses sur François. (Generalized colourings, digraphs and some things concerning François)
- Strong products of Kneser graphs
- A problem of Füredi and Seymour on covering intersecting families by pairs
- The order dimension of two levels of the Boolean lattices
- Tiling Hamming space with few spheres
- Circular chromatic number of Kneser graphs
- Vertex embeddings of regular polytopes
- Graph products and the chromatic difference sequence of vertex-transitive graphs
- The multichromatic numbers of some Kneser graphs
- On endo-homology of complexes of graphs
- Generalized Kneser coloring theorems with combinatorial proofs
- Homotopy type of neighborhood complexes of Kneser graphs, \(KG_{2,k}\)
- The neighborhood complexes of almost \(s\)-stable Kneser graphs
- Short proofs of the Kneser-Lovász coloring principle
- Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
- Vertex covering with monochromatic pieces of few colours
- Chromatic number of random Kneser hypergraphs
- A topological lower bound for the chromatic number of a special family of graphs
- On generalized Heawood inequalities for manifolds: a van Kampen-Flores-type nonembeddability result
- New construction of graphs with high chromatic number and small clique number
- Altermatic number of categorical product of graphs
- On the generalized Erdős-Kneser conjecture: proofs and reductions
- Independence number of products of Kneser graphs
- The chromatic number of the q-Kneser graph for large q
- Homotopy type of the neighborhood complexes of graphs of maximal degree at most 3 and 4-regular circulant graphs
- On multicolor Ramsey numbers for loose \(k\)-paths of length three
- A new lower bound for the chromatic number of general Kneser hypergraphs
- \(k\)-tuple colorings of the Cartesian product of graphs
- Existence of a \(P_{2 k + 1}\)-decomposition in the Kneser graph \(K G_{t, 2}\)
- Neighborhood and domination polynomials of graphs
- Topology of Hom complexes and test graphs for bounding chromatic number
- Extreme amenability of abelian L₀ groups
- Resource-sharing system scheduling and circular chromatic number
- Planar graphs are \(9/2\)-colorable
- On the chromatic number of a subgraph of the Kneser graph
- Stable sets of maximal size in Kneser-type graphs
- NP-completeness of a family of graph-colouring problems
- Un problème de partition de l'ensemble des parties à trois éléments d'un ensemble fini
- From graphs to ortholattices and equivariant maps
- Nearly bipartite graphs with large chromatic number
- 4-chromatic graphs with large odd girth
- Transversal numbers for hypergraphs arising in geometry
- Covering by intersecting families
- Box complexes, neighborhood complexes, and the chromatic number
- Coloring graph products---a survey
- Partitions of nonzero elements of a finite field into pairs
- Ideals of graph homomorphisms
- Reconfiguring graph homomorphisms on the sphere
- The \(p\)-restricted edge-connectivity of Kneser graphs
- Neighborhood complexes of Cayley graphs with generating set of size two
- Spectral gap bounds for the simplicial Laplacian and an application to random complexes
- Chromatic number via Turán number
- Coloring graphs by translates in the circle
- The toughness of Kneser graphs
- First-order complexity of subgraph isomorphism via Kneser graphs
- On the \(P_3\)-hull number of Kneser graphs
- Note on Hedetniemi's conjecture and the Poljak-Rödl function
- On the treewidth of Hanoi graphs
- The complexity of finding fair independent sets in cycles
- On the \(P_3\)-hull numbers of \(q\)-Kneser graphs and Grassmann graphs
- Neighborhood hypergraph model for topological data analysis
- Conflict-free coloring: graphs of bounded clique width and intersection graphs
- Fractional cocoloring of graphs
- Distributed algorithms for fractional coloring
- Treewidth of the generalized Kneser graphs
- Clique number of Xor products of Kneser graphs
- Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
- Aspects of topological approaches for data science
- The chromatic number of the product of 14-chromatic graphs can be 13
- On Vietoris-Rips complexes of hypercube graphs
This page was built for publication: Kneser's conjecture, chromatic number, and homotopy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q755592)
