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
• Groups synchronizing a transformation of non-uniform kernel
• Stiefel manifolds and coloring the pentagon
• Improved bounds on the chromatic numbers of the square of Kneser graphs
• Extremal problems related to Betti numbers of flag complexes
• Hypergraph coloring complexes
• On finite simple groups and Kneser graphs.
• Extremal problems concerning Kneser-graphs
• Independence numbers and chromatic numbers of some distance graphs
• A short proof of \(w_{1}^n (\text{Hom}(C_{2r+1}, K_{n+2})) = 0\) for all \(n\) and a graph colouring theorem by Babson and Kozlov
• Hamiltonian uniform subset graphs
• On random subgraphs of Kneser and Schrijver graphs
• Coloring the square of the Kneser graph \(\mathrm{KG}(2k+1,k)\) and the Schrijver graph \(\mathrm{SG}(2k+2,k)\)
• Graph colorings, spaces of edges and spaces of circuits
• On \(b\)-coloring of the Kneser graphs
• CORES OF SYMMETRIC GRAPHS
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
• Fractional chromatic numbers of cones over graphs
• On \(r\)-dynamic coloring of graphs
• Neighborhood complexes of some exponential graphs
• On the dynamic coloring of graphs
• Simple homotopy types of Hom-complexes, neighborhood complexes, Lovász complexes, and atom crosscut complexes
• Foldings in graphs and relations with simplicial complexes and posets
• Quadratic forms on graphs
• On the locating chromatic number of Kneser graphs
• Tight LP‐based lower bounds for wavelength conversion in optical networks
• Propositional proofs in Frege and extended Frege systems (abstract)
• A short proof of Kneser's conjecture
• Hom complexes and homotopy theory in the category of graphs
• Signature theory in holographic algorithms
• On colorings of graph powers
• Local coloring of Kneser graphs
• Graph products and the chromatic difference sequence of vertex-transitive graphs
• Nerve complexes of circular arcs
• A generalization of the Erdős-Ko-Rado theorem
• Stable sets of maximal size in Kneser-type graphs
• Chromatic capacity and graph operations
• Small models of graph colouring manifolds and the Stiefel manifolds \(\Hom(C_{5},K_n)\)
• \(k\)-tuple chromatic number of the Cartesian product of graphs
• Kneser transversals
• A combinatorial proof for the circular chromatic number of Kneser graphs
• Holographic algorithms: from art to science
• Topological obstructions for vertex numbers of Minkowski sums
• Circular coloring and Mycielski construction
• Mixing homomorphisms, recolorings, and extending circular precolorings
• On the diameter of Kneser graphs
• Complete Kneser transversals

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)