Distance graphs with large chromatic number and arbitrary girth

MaRDI QIDQ1946751zbMATH OpenFDO

Authors Andrey B. Kupavskii

Publication date 15 April 2013

Published in Moscow Journal of Combinatorics and Number Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.3921

zbMATH Keywords

chromatic numberdistance graphsforbidden subgraphsgirth

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Ramsey theory (05D10)

Abstract: In this article we consider a problem related to two famous combinatorial topics. One of them concerns the chromatic number of the space. The other deals with graphs having big girth (the length of the shortest cycle) and large chromatic number. Namely, we prove that for any $linmathbbN$ there exists a sequence of distance graphs in $mathbb{R}^n$ with girth at least $l$ and the chromatic number equal to $$ with $c>1$.

Recommendations

• On the structure of distance graphs with large chromatic numbers
• On the structure of distance graphs with a large chromatic number
• Distance graphs with large chromatic number and without large cliques
• Lower bounds for the chromatic numbers of distance graphs with large girth
• scientific article; zbMATH DE number 4118392
• Distance graphs with maximum chromatic number
• Distance graphs with maximum chromatic number
• Distance graphs with finite chromatic number

Cited in

(18)

• On the chromatic numbers of rational spaces
• On a Frankl-Rödl theorem and its geometric corollaries
• Distance graphs with large chromatic number and without large cliques
• On a Frankl-Wilson theorem
• Distance graphs with large chromatic number and without cliques of given size in the rational space
• Improved Frankl-Rödl theorem and some of its geometric consequences
• Counterexamples to Borsuk's conjecture with large girth
• Lower bounds for the chromatic numbers of distance graphs with large girth
• Improvements of the Frankl-Rödl theorem and geometric consequences
• Two notions of unit distance graphs
• On the Frankl-Rödl theorem
• scientific article; zbMATH DE number 4118392 (Why is no real title available?)
• scientific article; zbMATH DE number 1406333 (Why is no real title available?)
• Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii
• On a Frankl-Wilson theorem and its geometric corollaries
• The chromatic number of space with forbidden regular simplex
• Geometric Graphs with Exponential Chromatic Number and Arbitrary Girth
• On the graph of large distances

This page was built for publication: Distance graphs with large chromatic number and arbitrary girth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1946751)