Distance graphs with large chromatic numbers and small clique numbers

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

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)

Related Items

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, Hamiltonian paths in distance graphs, Zero-one laws for random graphs with vertices in a Boolean cube

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