Kneser's conjecture, chromatic number, and homotopy

DOI10.1016/0097-3165(78)90022-5zbMATH Open0418.05028DBLPjournals/jct/Lovasz78OpenAlexW2003995429WikidataQ29308588 ScholiaQ29308588MaRDI QIDQ755592FDOQ755592

Authors: László Lovász 

Publication date: 1978

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(78)90022-5

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

zbMATH Keywords

simplicial complexKneser conjectureneighborhoods of points of a graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• n-tuple colorings and associated graphs
• On chromatic number of graphs and set-systems
• Title not available (Why is that?)
• The Complexity of Near-Optimal Graph Coloring

Cited In (only showing first 100 items - show all)

• Box complexes, neighborhood complexes, and the chromatic number
• Hedetniemi's conjecture and adjoint functors in thin categories
• On \(q\)-analogues and stability theorems
• On endo-homology of complexes of graphs
• Hedetniemi's conjecture for Kneser hypergraphs
• Long induced paths and cycles in Kneser graphs
• On graphs with strongly independent color-classes
• Colorful subhypergraphs in Kneser hypergraphs
• Hypergraphs with many Kneser colorings
• Chromatic number of random Kneser hypergraphs
• On the chromatic number of general Kneser hypergraphs
• The chromatic number of almost stable Kneser hypergraphs
• Non-projectability of polytope skeleta
• On the topological lower bound for the multichromatic number
• Colouring lines in projective space
• Chromatic number via Turán number
• Sharp bounds for the chromatic number of random Kneser graphs
• The colored Tverberg's problem and complexes of injective functions
• Helly property in finite set systems
• Strengthening topological colorful results for graphs
• The chromatic Ramsey number of odd wheels
• Four-cycled graphs with topological applications
• Homomorphism complexes and \(k\)-cores
• On colorful edge triples in edge-colored complete graphs
• The maximum size of a partial spread in a finite projective space
• Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem
• Density and power graphs in graph homomorphism problem
• On the b-chromatic number of Kneser graphs
• Arrangements of \(k\)-sets with intersection constraints
• On weak \(\epsilon\)-nets and the Radon number
• Proof of the middle levels conjecture
• On inverse powers of graphs and topological implications of Hedetniemi's conjecture
• The \(p\)-restricted edge-connectivity of Kneser graphs
• The chromatic connectivity of graphs
• On constructive methods in the theory of colour-critical graphs
• On the chromatic number of Kneser hypergraphs
• A generalization of Kneser's conjecture
• Counterexamples to a conjecture on matching Kneser graphs
• Answers to some problems about graph coloring test graphs
• Paths of homomorphisms from stable Kneser graphs
• A certain combinatorial inequality
• The equivariant topology of stable Kneser graphs
• Covering by intersecting families
• The neighborhood complex of a random graph
• Homotopy types of box complexes
• Decompositions into subgraphs of small diameter
• Symmetries of the stable Kneser graphs
• Vertex embeddings of regular polytopes
• A new lower bound for the chromatic number of general Kneser hypergraphs
• A new spectral sequence for homology of posets
• A generalization of the ham sandwich theorem
• Linear colorings of simplicial complexes and collapsing
• On the chromatic number of \(H\)-free graphs of large minimum degree
• Colorful subhypergraphs in uniform hypergraphs
• The achromatic number of Kneser graphs
• \(L(2,1)\)-labeling of Kneser graphs and coloring squares of Kneser graphs
• A counterexample to a conjecture of Björner and Lovász on the \(\chi\)-coloring complex
• Prodsimplicial-neighborly polytopes
• Covering radius and the chromatic number of Kneser graphs
• Independent sets in the union of two Hamiltonian cycles
• Random Kneser graphs and hypergraphs
• Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits
• \(b\)-coloring of Kneser graphs
• Ideals of graph homomorphisms
• Shifts of the stable Kneser graphs and hom-idempotence
• Maximum bipartite subgraphs of Kneser graphs
• The geometry and topology of reconfiguration
• Independence number of products of Kneser graphs
• Colouring quadrangulations of projective spaces
• Topological graph persistence
• The neighborhood polynomial of chordal graphs
• Hajós-type constructions and neighborhood complexes
• Large disjoint subgraphs with the same order and size
• Edge-critical subgraphs of Schrijver graphs. II: The general case
• Homotopy types of box complexes of chordal graphs
• Intersection patterns of finite sets and of convex sets
• On the circular chromatic number of graph powers
• Homotopy types of the Hom complexes of graphs
• Extreme amenability of abelian \(L_0\) groups
• Neighborhood and domination polynomials of graphs
• Extremal \(G\)-free induced subgraphs of Kneser graphs
• WI-posets, graph complexes and \(\mathbb{Z}_2\)-equivalences
• On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs
• Chromatic Ramsey number of acyclic hypergraphs
• Homomorphism complexes, reconfiguration, and homotopy for directed graphs
• Homomorphism complexes, reconfiguration, and homotopy for directed graphs
• Exact distance graphs of product graphs
• On the \(P_3\)-hull numbers of \(q\)-Kneser graphs and Grassmann graphs
• Geodetic convexity and Kneser graphs
• Colorful flowers
• Graph operations and neighborhood polynomials
• Large independent sets in shift-invariant graphs
• Tverberg’s theorem is 50 years old: A survey
• The Borsuk--Ulam-property, Tucker-property and constructive proofs in combinatorics
• Homology as a Tool in Integer Programming
• The graphs behind reuleaux polyhedra
• Subgraphs of Kneser graphs with large girth and large chromatic number
• A class of additive multiplicative graph functions
• Finite convergence of sum-of-squares hierarchies for the stability number of a graph
• A note on the chromatic number of the square of Kneser graph \(K(2 k + 1, k)\)

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)