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)

• 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)\)
• Generalized fractional and circular total colorings of graphs
• Edge-critical subgraphs of Schrijver graphs
• \(k\)-tuple colorings of the Cartesian product of graphs
• A new approach to the chromatic number of the square of Kneser graph \(K(2k+1,k)\)
• Hom complexes and homotopy in the category of graphs
• 4-chromatic graphs with large odd girth
• Vizing's conjecture for chordal graphs
• Häggkvist-Hell graphs: A class of Kneser-colorable graphs
• Coloring of the square of Kneser graph \(K(2k+r,k)\)
• From graphs to ortholattices and equivariant maps
• Topological bounds on the dimension of orthogonal representations of graphs
• Graph classes with linear Ramsey numbers
• Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
• A note on Hedetniemi's conjecture, Stahl's conjecture and the Poljak-Rödl function
• A note on the Poljak-Rödl function
• Topological obstructions to graph colorings
• Homomorphism complexes and maximal chains in graded posets
• Colorings of complements of line graphs
• Schrijver graphs and projective quadrangulations
• Non-cover generalized Mycielski, Kneser, and Schrijver graphs
• The genus of \(G\)-spaces and topological lower bounds for chromatic numbers of hypergraphs
• Conflict-free coloring: graphs of bounded clique width and intersection graphs
• Homotopy groups of Hom complexes of graphs
• Coloring graph products---a survey
• Orthogonal partitions and covering of graphs
• 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

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)