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

zbMATH Keywords

cyclechromatic numberdistance graphclique numbercliqueprobabilistic methodrandom graphEuclidean distance graph

Mathematics Subject Classification ID

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

• 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

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