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)

• 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
• Transversals to the convex hulls of all \(k\)-sets of discrete subsets of \(\mathbb R^n\)
• A generalized Kneser conjecture
• Topology and combinatorics of partitions of masses by hyperplanes
• A combinatorial approach to nonlocality and contextuality
• Independence and coloring properties of direct products of some vertex-transitive graphs
• Generalised Mycielski graphs, signature systems, and bounds on chromatic numbers
• Square-free graphs are multiplicative
• Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
• Star clusters in independence complexes of graphs
• The universality of Hom complexes of graphs
• Topological methods in combinatorial problems
• Partitions of nonzero elements of a finite field into pairs
• Complexes of graph homomorphisms
• Resource-sharing system scheduling and circular chromatic number
• Colorful subgraphs in Kneser-like graphs
• On topological relaxations of chromatic conjectures
• Circular chromatic number of Kneser graphs
• On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges
• Some remarks on Hajós' conjecture
• The multichromatic numbers of some Kneser graphs
• On the chromatic number of some geometric type Kneser graphs
• Generalized Kneser coloring theorems with combinatorial proofs
• A result on polynomials derived via graph theory
• Combinatorial groupoids, cubical complexes, and the Lovász Conjecture
• On directed local chromatic number, shift graphs, and Borsuk-like graphs
• Transversal numbers for hypergraphs arising in geometry
• Circular colouring and algebraic no-homomorphism theorems
• The Chromatic Number of Kneser Hypergraphs
• The existence of a near-unanimity term in a finite algebra is decidable
• Color the cycles
• On homometric sets in graphs
• Local chromatic number and distinguishing the strength of topological obstructions
• Topology of Hom complexes and test graphs for bounding chromatic number
• A combinatorial development of Fibonacci numbers in graph spectra
• A new coloring theorem of Kneser graphs
• Hom complexes and hypergraph colorings
• 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

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)