Distance graphs with large chromatic numbers and small clique numbers
From MaRDI portal
Publication:1761033
DOI10.1134/S1064562412030295zbMath1254.05058arXiv1202.2968MaRDI QIDQ1761033
Andrei M. Raigorodskii, Andrey B. Kupavskii, O. I. Rubanov, E. E. Demekhin
Publication date: 15 November 2012
Published in: Doklady Mathematics, Sbornik: Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1202.2968
cycle; chromatic number; distance graph; clique number; clique; probabilistic method; random graph; Euclidean distance graph
05C35: Extremal problems in graph theory
05C80: Random graphs (graph-theoretic aspects)
05C15: Coloring of graphs and hypergraphs
05C12: Distance in graphs
05D10: Ramsey theory
Related Items
Zero-one laws for random graphs with vertices in a Boolean cube, Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii, Independence numbers of random subgraphs of a distance graph, On the number of edges in induced subgraphs of a special distance graph, A new estimate for the number of edges in induced subgraphs of a special distance graph, On the stability of the Erdös-Ko-Rado theorem, The chromatic number of space with forbidden regular simplex, Hamiltonian paths in distance graphs, On the chromatic numbers of rational spaces, Diameters of random distance graphs, On a Frankl-Rödl theorem and its geometric corollaries, Chromatic numbers of distance graphs without short odd cycles in rational spaces, Chromatic numbers of distance graphs with several forbidden distances and without cliques of a given size, On a Frankl-Wilson theorem, Estimate of the number of edges in special subgraphs of a distance graph, Zero-one laws for random distance graphs with vertices in \(\{0,1\}^n\), Distance graphs with large chromatic number and without cliques of given size in the rational space, Lower bounds for the chromatic numbers of distance graphs with large girth
Cites Work
- Chromatic numbers of 3-dimensional distance graphs containing no tetrahedra
- Intersection theorems with geometric consequences
- A 15-colouring of 3-space omitting distance one
- On the space chromatic number
- Finite Euclidean Ramsey theory
- Distance graphs with large chromatic number and without large cliques
- Die Kugel als Körper extremaler Korona
- The Difference Between Consecutive Primes, II
- Borsuk's problem and the chromatic numbers of some metric spaces
- Research Problems in Discrete Geometry
- Graph Theory and Probability
- The problems of Borsuk and Grunbaum on lattice polytopes
- On Ramsey Type Problems in Combinatorial Geometry
- The Mathematical Coloring Book
- An estimate for the chromatic number of the space $ \mathbb R^4$
- On distance graphs with large chromatic number but without large simplices
- Chromatic numbers of real and rational spaces with real or rational forbidden distances
- Estimating the chromatic numbers of Euclidean space by convex minimization methods
- On the chromatic number of a space
- The realization of distances within sets in Euclidean space
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item