Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs
From MaRDI portal
Publication:2422241
DOI10.1016/j.ejc.2019.03.004zbMath1414.05107arXiv1805.09394OpenAlexW2963036780WikidataQ128071844 ScholiaQ128071844MaRDI QIDQ2422241
Sergei Kiselev, József Balogh, Danila Cherkashin
Publication date: 18 June 2019
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.09394
Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15)
Related Items
On Two Limit Values of the Chromatic Number of a Random Hypergraph ⋮ Large cycles in generalized Johnson graphs ⋮ Estimate of the number of edges in special subgraphs of a distance graph ⋮ A generalization of Kneser graphs ⋮ The list-chromatic number of complete multipartite hypergraphs and multiple covers by independent sets ⋮ New bounds on clique-chromatic numbers of Johnson graphs ⋮ On the diameter and zero forcing number of some graph classes in the Johnson, Grassmann and Hamming association scheme ⋮ 2-colorings of hypergraphs with large girth ⋮ On the independence number and the chromatic number of generalized preferential attachment models ⋮ Extremal problems in hypergraph colourings ⋮ Lower bound on the minimum number of edges in subgraphs of Johnson graphs ⋮ Geodetic convexity and Kneser graphs ⋮ Exact modularity of line graphs of complete graphs ⋮ New lower bound on the modularity of Johnson graphs ⋮ On stability of the independence number of a certain distance graph ⋮ Modularity of some distance graphs ⋮ New bounds for the clique-chromatic numbers of Johnson graphs ⋮ On the chromatic number of generalized Kneser graphs and Hadamard matrices ⋮ Exact distance graphs of product graphs ⋮ Lower bounds on the clique-chromatic numbers of some distance graphs ⋮ Chromatic numbers of Kneser-type graphs ⋮ Systems of representatives ⋮ On the independence numbers of distance graphs with vertices in \(\{-1, 0, 1\}^n\) ⋮ On the chromatic number of generalized Kneser hypergraphs ⋮ New lower bound for the minimal number of edges of simple uniform hypergraph without the property \(B_k\) ⋮ Asymptotics of the independence number of a random subgraph of the graph \(G(n,r,<s)\)
Cites Work
- Unnamed Item
- The complete intersection theorem for systems of finite sets
- Kneser's conjecture, chromatic number, and homotopy
- On the diameter of generalized Kneser graphs
- Extremal problems concerning Kneser-graphs
- Intersection theorems with geometric consequences
- On the ratio of optimal integral and fractional covers
- Generalized Kneser coloring theorems with combinatorial proofs
- Intersection theorems for \(\{0,\pm1\}\)-vectors and \(s\)-cross-intersecting families
- Erdős-Ko-Rado theorem for \(\{0,\pm 1\}\)-vectors
- A combinatorical proof of Kneser's conjecture
- Clique chromatic numbers of intersection graphs
- On chromatic numbers of close-to-Kneser distance graphs
- On the girth and diameter of generalized Johnson graphs
- Families of vectors without Antipodal pairs
- On the chromatic number of the general Kneser-graph
- Six Standard Deviations Suffice
- The Chromatic Number of Kneser Hypergraphs
- On the chromatic number of Kneser hypergraphs
- On the chromatic numbers of small-dimensional Euclidean spaces
- 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
- Combinatorial algebraic topology
