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)

• Borsuk's theorem through complementary pivoting
• Deformation retracts of neighborhood complexes of stable Kneser graphs
• On the multichromatic number of \(s\)-stable Kneser graphs
• Tight lower bounds for the complexity of multicoloring
• The chromatic number of the \(q\)-Kneser graph for large \(q\)
• The Neighborhood Polynomial of Chordal Graphs
• Chromatic numbers of Kneser-type graphs
• Short proofs of the Kneser-Lovász coloring principle
• Short proofs of the Kneser-Lovász coloring principle
• Homotopy type of the neighborhood complexes of graphs of maximal degree at most 3 and 4-regular circulant graphs
• Large cycles in generalized Johnson graphs
• On total and edge coloring some Kneser graphs
• The complexity of multicolouring
• Tiling Hamming space with few spheres
• NP-completeness of a family of graph-colouring problems
• Multicolor Ramsey numbers for triple systems
• The algebra of flows in graphs
• Families of nested graphs with compatible symmetric-group actions
• Homotopy type of neighborhood complexes of Kneser graphs, \(KG_{2,k}\)
• On locally-perfect colorings
• A combinatorial proof of the Borsuk-Ulam antipodal point theorem
• On multicolor Ramsey numbers for loose \(k\)-paths of length three
• Existence of a \(P_{2 k + 1}\)-decomposition in the Kneser graph \(K G_{t, 2}\)
• Dichromatic number and fractional chromatic number
• The neighborhood complexes of almost \(s\)-stable Kneser graphs
• The order dimension of two levels of the Boolean lattices
• On the generalized Erdős-Kneser conjecture: proofs and reductions
• On the \(P_3\)-hull number of Kneser 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)
• Decomposition of the Kneser graph into paths of length four
• Treewidth of the generalized Kneser graphs
• A generalization of Kneser graphs
• Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
• Orthogonality spaces associated with posets
• Achromatic numbers of Kneser graphs
• On multichromatic numbers of widely colorable graphs
• On the bandwidth of the Kneser graph
• A note on fractional covers of a graph
• On the neighborhood complex of \(\overrightarrow{s} \)-stable Kneser graphs
• Bipartite Kneser graphs are Hamiltonian
• Title not available (Why is that?)
• Vertex covering with monochromatic pieces of few colours
• A note on induced cycles in Kneser graphs
• Strong products of Kneser graphs
• Title not available (Why is that?)
• A problem of Füredi and Seymour on covering intersecting families by pairs
• Twins in graphs
• 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
• Multi-coloring the Mycielskian of graphs
• Generalised Mycielski graphs and the Borsuk-Ulam theorem
• New construction of graphs with high chromatic number and small clique number
• Altermatic number of categorical product of graphs
• On weak \(\varepsilon\)-nets and the Radon number
• 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

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)