Kneser's conjecture, chromatic number, and homotopy
From MaRDI portal
Publication:755592
DOI10.1016/0097-3165(78)90022-5zbMath0418.05028OpenAlexW2003995429WikidataQ29308588 ScholiaQ29308588MaRDI QIDQ755592
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
Related Items
Topology and Adjunction in Promise Constraint Satisfaction, Disjointness graphs of segments in the space, The chromatic profile of locally colourable graphs, Hom complexes and homotopy in the category of graphs, CORES OF SYMMETRIC GRAPHS, Vertex cut of a graph and connectivity of its neighbourhood complex, On the connectivity of the disjointness graph of segments of point sets in general position in the plane, The Neighborhood Polynomial of Chordal Graphs, A counterexample to a conjecture on the chromatic number of r $r$‐stable Kneser hypergraphs, Colorings of complements of line graphs, On multichromatic numbers of widely colorable graphs, The core of a complementary prism, Large cycles in generalized Johnson graphs, Local orthogonality dimension, Independence numbers of Johnson-type graphs, A Result on Polynomials Derived Via Graph Theory, Concerning a conjecture on matching Kneser graphs, Unnamed Item, On the diameter of Schrijver graphs, On finding constrained independent sets in cycles, Orthogonality spaces associated with posets, On the number of star‐shaped classes in optimal colorings of Kneser graphs, Fixed-Parameter Algorithms for the Kneser and Schrijver Problems, Total dominator chromatic number of Kneser graphs, Disjointness graphs of segments in \(\mathbb{R}^2\) are almost all Hamiltonian, Treewidth of the \(q\)-Kneser graphs, Tight Lower Bounds for the Complexity of Multicoloring, Trivial colors in colorings of Kneser graphs, Graphs of large chromatic number, Monochromatic spanning trees and matchings in ordered complete graphs, Triangle-free subgraphs with large fractional chromatic number, Bipartite Kneser graphs are Hamiltonian, Unnamed Item, A generalization of Kneser's conjecture, Bipartite Kneser graphs are Hamiltonian, Hajós-Type Constructions and Neighborhood Complexes, Deformation retracts of neighborhood complexes of stable Kneser graphs, Quadratic forms on graphs, Topological Bounds for Graph Representations over Any Field, Tight LP‐based lower bounds for wavelength conversion in optical networks, Equipartitions of measures in $\mathbb{R}^4$, Morphism complexes of sets with relations, Homomorphism complexes, reconfiguration, and homotopy for directed graphs, Grundy domination and zero forcing in Kneser graphs, Noncommutative network models, On the Chromatic Number of Matching Kneser Graphs, Fractional Coloring Methods with Applications to Degenerate Graphs and Graphs on Surfaces, Multilabeled Versions of Sperner's and Fan's Lemmas and Applications, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, On the Multichromatic Number of s‐Stable Kneser Graphs, On random subgraphs of Kneser and Schrijver graphs, On \(r\)-dynamic coloring of graphs, Topological graph persistence, Neighborhood complexes of some exponential graphs, The neighborhood polynomial of chordal 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, Nerve complexes of circular arcs, Large independent sets in shift-invariant graphs, \(k\)-tuple chromatic number of the Cartesian product of graphs, Kneser transversals, A combinatorial proof for the circular chromatic number of Kneser graphs, A class of additive multiplicative graph functions, Topology and combinatorics of partitions of masses by hyperplanes, Complete Kneser transversals, The chromatic connectivity of graphs, Square-free graphs are multiplicative, Generalised Mycielski graphs, signature systems, and bounds on chromatic numbers, The complexity of multicolouring, The neighborhood complex of a random graph, Maximum bipartite subgraphs of Kneser graphs, On constructive methods in the theory of colour-critical graphs, On locally-perfect colorings, A certain combinatorial inequality, Color the cycles, A combinatorial development of Fibonacci numbers in graph spectra, Hom complexes and hypergraph colorings, Star clusters in independence complexes of graphs, 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, Transversals to the convex hulls of all \(k\)-sets of discrete subsets of \(\mathbb R^n\), On the dynamic coloring of graphs, Extremal problems related to Betti numbers of flag complexes, Holographic algorithms: from art to science, Colorful subhypergraphs in Kneser hypergraphs, Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem, On \(q\)-analogues and stability theorems, Hypergraphs with many Kneser colorings, Four-cycled graphs with topological applications, Hypergraph coloring complexes, Foldings in graphs and relations with simplicial complexes and posets, The equivariant topology of stable Kneser graphs, Arrangements of \(k\)-sets with intersection constraints, Signature theory in holographic algorithms, Non-projectability of polytope skeleta, On the chromatic number of \(H\)-free graphs of large minimum degree, Density and power graphs in graph homomorphism problem, Answers to some problems about graph coloring test graphs, Paths of homomorphisms from stable Kneser graphs, On the chromatic number of general Kneser hypergraphs, Independent sets in the union of two Hamiltonian cycles, Random Kneser graphs and hypergraphs, Non-cover generalized Mycielski, Kneser, and Schrijver graphs, A new spectral sequence for homology of posets, Homotopy types of box complexes, Colorful subhypergraphs in uniform hypergraphs, The genus of \(G\)-spaces and topological lower bounds for chromatic numbers of hypergraphs, The achromatic number of Kneser graphs, \(L(2,1)\)-labeling of Kneser graphs and coloring squares of Kneser graphs, Hedetniemi's conjecture and adjoint functors in thin categories, Shifts of the stable Kneser graphs and hom-idempotence, Hedetniemi's conjecture for Kneser hypergraphs, On the topological lower bound for the multichromatic number, Homotopy types of box complexes of chordal graphs, On the b-chromatic number of Kneser graphs, On finite simple groups and Kneser graphs., Circular coloring and Mycielski construction, Prodsimplicial-neighborly polytopes, The chromatic number of almost stable Kneser hypergraphs, Symmetries of the stable Kneser graphs, Some remarks on Hajós' conjecture, On topological relaxations of chromatic conjectures, The universality of Hom complexes of graphs, Homomorphism complexes and \(k\)-cores, Extremal \(G\)-free induced subgraphs of Kneser graphs, Chromatic Ramsey number of acyclic hypergraphs, Local coloring of Kneser graphs, Hom complexes and homotopy theory in the category of graphs, Topological obstructions for vertex numbers of Minkowski sums, Homotopy groups of Hom complexes of graphs, Coloring the square of the Kneser graph \(\mathrm{KG}(2k+1,k)\) and the Schrijver graph \(\mathrm{SG}(2k+2,k)\), Combinatorial groupoids, cubical complexes, and the Lovász Conjecture, Colorful flowers, A generalized Kneser conjecture, Large disjoint subgraphs with the same order and size, Vizing's conjecture for chordal graphs, Graph colorings, spaces of edges and spaces of circuits, Häggkvist-Hell graphs: A class of Kneser-colorable graphs, On the locating chromatic number of Kneser graphs, \(b\)-coloring of Kneser graphs, Edge-critical subgraphs of Schrijver graphs, On colorings of graph powers, On \(b\)-coloring of the Kneser graphs, A note on the Poljak-Rödl function, A generalization of the Erdős-Ko-Rado theorem, Extremal problems concerning Kneser-graphs, Covering radius and the chromatic number of Kneser graphs, Hamiltonian uniform subset graphs, Independence numbers and chromatic numbers of some distance graphs, Colouring lines in projective space, Treewidth of the generalized Kneser graphs, Covering by intersecting families, Box complexes, neighborhood complexes, and the chromatic number, Strong products of Kneser graphs, A problem of Füredi and Seymour on covering intersecting families by pairs, The order dimension of two levels of the Boolean lattices, Homotopy type of neighborhood complexes of Kneser graphs, \(KG_{2,k}\), The neighborhood complexes of almost \(s\)-stable Kneser graphs, Clique number of Xor products of Kneser graphs, Graph theory -- a survey on the occasion of the Abel Prize for László Lovász, Short proofs of the Kneser-Lovász coloring principle, Aspects of topological approaches for data science, The chromatic number of the product of 14-chromatic graphs can be 13, On Vietoris-Rips complexes of hypercube graphs, Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization, Choice number of Kneser graphs, On total and edge coloring some Kneser graphs, Tiling Hamming space with few spheres, Sharp bounds for the chromatic number of random Kneser graphs, Vertex covering with monochromatic pieces of few colours, The geometry and combinatorics of discrete line segment hypergraphs, A combinatorial proof of the Borsuk-Ulam antipodal point theorem, Coloring graph products---a survey, Chromatic number of random Kneser hypergraphs, Bisecting and \(D\)-secting families for set systems, On semi-transitive orientability of Kneser graphs and their complements, Partitions of nonzero elements of a finite field into pairs, 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, A generalization of Kneser graphs, Circular chromatic number of Kneser graphs, Proof of Stahl's conjecture in some new cases, New construction of graphs with high chromatic number and small clique number, Ideals of graph homomorphisms, The graphs behind reuleaux polyhedra, Altermatic number of categorical product of graphs, Vertex embeddings of regular polytopes, On the generalized Erdős-Kneser conjecture: proofs and reductions, On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges, On some topological and combinatorial lower bounds on the chromatic number of Kneser type hypergraphs, On weak \(\epsilon\)-nets and the Radon number, Independence number of products of Kneser graphs, A note on induced cycles in Kneser graphs, The chromatic number of the \(q\)-Kneser graph for large \(q\), Vanishing of all equivariant obstructions and the mapping degree, Neighborhood complexes and Kronecker double coverings, Homotopy type of the neighborhood complexes of graphs of maximal degree at most 3 and 4-regular circulant graphs, Reconfiguring graph homomorphisms on the sphere, On multicolor Ramsey numbers for loose \(k\)-paths of length three, A new lower bound for the chromatic number of general Kneser hypergraphs, \(k\)-tuple colorings of the Cartesian product of graphs, Existence of a \(P_{2 k + 1}\)-decomposition in the Kneser graph \(K G_{t, 2}\), The colored Tverberg's problem and complexes of injective functions, Neighborhood and domination polynomials of graphs, Topology of Hom complexes and test graphs for bounding chromatic number, A generalization of the ham sandwich theorem, Helly property in finite set systems, Extreme amenability of abelian \(L_0\) groups, A combinatorial approach to nonlocality and contextuality, The \(p\)-restricted edge-connectivity of Kneser graphs, Neighborhood complexes of Cayley graphs with generating set of size two, Spectral gap bounds for the simplicial Laplacian and an application to random complexes, Chromatic number via Turán number, Resource-sharing system scheduling and circular chromatic number, A note on Hedetniemi's conjecture, Stahl's conjecture and the Poljak-Rödl function, On the Hadwiger number of Kneser graphs and their random subgraphs, A note on the chromatic number of the square of Kneser graph \(K(2 k + 1, k)\), On the chromatic number of generalized Kneser graphs and Hadamard matrices, A note on homomorphisms of Kneser hypergraphs, Coloring graphs by translates in the circle, Planar graphs are \(9/2\)-colorable, On the chromatic number of a subgraph of the Kneser graph, Exact distance graphs of product graphs, The toughness of Kneser graphs, First-order complexity of subgraph isomorphism via Kneser graphs, A short proof of Kneser's conjecture, Dold's theorem from viewpoint of strong compatibility graphs, On the \(P_3\)-hull number of Kneser graphs, Chromatic numbers of Kneser-type graphs, Long induced paths and cycles in Kneser graphs, Note on Hedetniemi's conjecture and the Poljak-Rödl function, The algebra of flows in graphs, Stable sets of maximal size in Kneser-type graphs, On the treewidth of Hanoi graphs, NP-completeness of a family of graph-colouring problems, Un problème de partition de l'ensemble des parties à trois éléments d'un ensemble fini, From graphs to ortholattices and equivariant maps, Nearly bipartite graphs with large chromatic number, 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), 4-chromatic graphs with large odd girth, The complexity of finding fair independent sets in cycles, Graph products and the chromatic difference sequence of vertex-transitive graphs, The multichromatic numbers of some Kneser graphs, On endo-homology of complexes of graphs, On the \(P_3\)-hull numbers of \(q\)-Kneser graphs and Grassmann graphs, Neighborhood hypergraph model for topological data analysis, Transversal numbers for hypergraphs arising in geometry, Conflict-free coloring: graphs of bounded clique width and intersection graphs, Fractional cocoloring of graphs, Distributed algorithms for fractional coloring, Strengthening topological colorful results for graphs, The automorphism group of the \(s\)-stable Kneser graphs, An infinite family of incidence geometries whose incidence graphs are locally X, Circular colouring and algebraic no-homomorphism theorems, Short Proofs of the Kneser-Lovász Coloring Principle, Homology as a Tool in Integer Programming, The \((p, q)\)-extremal problem and the fractional chromatic number of Kneser hypergraphs, Coloring of the square of Kneser graph \(K(2k+r,k)\), A note on fractional covers of a graph, Subgraphs of Kneser graphs with large girth and large chromatic number, Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone, Complexes of graph homomorphisms, Linear colorings of simplicial complexes and collapsing, On the chromatic number of some geometric type Kneser graphs, Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings, Finite Convergence of Sum-of-Squares Hierarchies for the Stability Number of a Graph, Propositional Proofs in Frege and Extended Frege Systems (Abstract), Graph operations and neighborhood polynomials, Shannon capacity and the categorical product, Codimension Two and Three Kneser Transversals, On colorful edge triples in edge-colored complete graphs, The maximum size of a partial spread in a finite projective space, On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs, Graphs whose Kronecker covers are bipartite Kneser graphs, On the neighborhood complex of \(\overrightarrow{s} \)-stable Kneser graphs, Graph classes with linear Ramsey numbers, 1-subdivisions, the fractional chromatic number and the Hall ratio, Topology of tropical moduli of weighted stable curves, Edge-critical subgraphs of Schrijver graphs. II: The general case, A new approach to the chromatic number of the square of Kneser graph \(K(2k+1,k)\), Warmth and edge spaces of graphs, Set labelling vertices to ensure adjacency coincides with disjointness, COLORING CURVES ON SURFACES, Neighborhood complexes, homotopy test graphs and an application to coloring of product graphs, Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs, Hedetniemi's conjecture from the topological viewpoint, Unnamed Item, On the boxicity of Kneser graphs and complements of line graphs, On the chromatic number of Kneser hypergraphs, A new coloring theorem of Kneser graphs, Schrijver Graphs and Projective Quadrangulations, DICHROMATIC NUMBER AND FRACTIONAL CHROMATIC NUMBER, Multicolor Ramsey numbers for triple systems, Geodetic convexity and Kneser graphs, Homomorphism complexes, reconfiguration, and homotopy for directed graphs, Coloring properties of categorical product of general Kneser hypergraphs, Circular chromatic number of induced subgraphs of Kneser graphs, Twins in graphs, Intersection patterns of finite sets and of convex sets, Lovász, Vectors, Graphs and Codes, The geometry and topology of reconfiguration, Multi-coloring the Mycielskian of graphs, Colorful subgraphs in Kneser-like graphs, Orthogonal partitions and covering of graphs, Unnamed Item, On homometric sets in graphs, Discretized configurations and partial partitions, Small models of graph colouring manifolds and the Stiefel manifolds \(\Hom(C_{5},K_n)\), Decompositions into Subgraphs of Small Diameter, Fractional chromatic numbers of cones over graphs, Chromatic capacity and graph operations, The Chromatic Number of Kneser Hypergraphs, The Borsuk--Ulam-property, Tucker-property and constructive proofs in combinatorics, Topological obstructions to graph colorings, Unnamed Item, Simple homotopy types of Hom-complexes, neighborhood complexes, Lovász complexes, and atom crosscut complexes, Tverberg’s theorem is 50 years old: A survey, Unnamed Item, Colinear Coloring on Graphs, Local chromatic number and distinguishing the strength of topological obstructions, Independence and coloring properties of direct products of some vertex-transitive graphs, On directed local chromatic number, shift graphs, and Borsuk-like graphs, Generalized fractional and circular total colorings of graphs, Proof of the middle levels conjecture, Borsuk's theorem through complementary pivoting, Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits, The existence of a near-unanimity term in a finite algebra is decidable, Computing a small agreeable set of indivisible items, On the chromatic number of random subgraphs of a certain distance graph, Topological bounds on the dimension of orthogonal representations of graphs, On the chromatic number of generalized Kneser hypergraphs, Homomorphism complexes and maximal chains in graded posets, \(\mathbb{Z}_2\)-indices and Hedetniemi's conjecture, The chromatic Ramsey number of odd wheels, On graphs with strongly independent color-classes, Generalised Mycielski graphs and the Borsuk-Ulam theorem, WI-posets, graph complexes and \(\mathbb{Z}_2\)-equivalences, Families of nested graphs with compatible symmetric-group actions, Sparse Kneser graphs are Hamiltonian, A counterexample to a conjecture of Björner and Lovász on the \(\chi\)-coloring complex, On chromatic number and minimum cut, On inverse powers of graphs and topological implications of Hedetniemi's conjecture, Achromatic numbers of Kneser graphs, Decomposition of the Kneser graph into paths of length four, On the diameter of Kneser graphs, Colouring quadrangulations of projective spaces, On the Circular Chromatic Number of Graph Powers, On maximal isolation sets in the uniform intersection matrix, On the bandwidth of the Kneser graph, Homotopy types of the Hom complexes of graphs
Cites Work
