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)
Abstract: In this work, the classical Nelson -- Hadwiger problem is studied which lies on the edge of combinatorial geometry and graph theory. It concerns colorings of distance graphs in $ {mathbb R}^n $, i.e., graphs such that their vertices are vectors and their edges are pairs of vectors at a distance from a given set of postive numbers apart. A series of new lower bounds are obtained for the chromatic numbers of such graphs with different restrictions on the clique numbers and the girths.
Full work available at URL: https://arxiv.org/abs/1202.2968
cyclechromatic numberdistance graphclique numbercliqueprobabilistic methodrandom graphEuclidean distance graph
Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Ramsey theory (05D10)
Cites Work
- 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
- 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
Related Items (19)
Lower bounds for the chromatic numbers of distance graphs with large girth ⋮ 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 chromatic numbers of rational spaces ⋮ Diameters of random distance graphs ⋮ Chromatic numbers of distance graphs with several forbidden distances and without cliques of a given size ⋮ On a Frankl-Wilson theorem ⋮ On a Frankl-Rödl theorem and its geometric corollaries ⋮ Estimate of the number of edges in special subgraphs of a distance graph ⋮ Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii ⋮ On the stability of the Erdös-Ko-Rado theorem ⋮ The chromatic number of space with forbidden regular simplex ⋮ 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 ⋮ Chromatic numbers of distance graphs without short odd cycles in rational spaces ⋮ On a Frankl-Wilson theorem and its geometric corollaries ⋮ Hamiltonian paths in distance graphs ⋮ Zero-one laws for random graphs with vertices in a Boolean cube
This page was built for publication: Distance graphs with large chromatic numbers and small clique numbers
