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
• 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

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)