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 numbergirthforbidden subgraphsdistance graphs

Mathematics Subject Classification ID

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

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)