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

cycle; chromatic number; distance graph; clique number; clique; probabilistic method; random graph; Euclidean distance graph

Mathematics Subject Classification ID

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