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

(17)

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

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)