Distance graphs with large chromatic number and arbitrary girth

zbMATH Open1270.05044arXiv1306.3921MaRDI QIDQ1946751FDOQ1946751

Andrey B. Kupavskii

Publication date: 15 April 2013

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

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$.

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

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 numbers and small clique numbers
• 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 large chromatic numbers and small clique numbers
• Distance graphs with finite chromatic number

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)

Cited In (16)

• On the graph of large distances
• Title not available (Why is that?)
• On a Frankl-Wilson theorem
• Title not available (Why is that?)
• On a Frankl-Rödl theorem and its geometric corollaries
• Improvements of the Frankl-Rödl theorem and geometric consequences
• Lower bounds for the chromatic numbers of distance graphs with large girth
• On a Frankl-Wilson theorem and its geometric corollaries
• On the chromatic numbers of rational spaces
• Two notions of unit distance graphs
• 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
• On the Frankl–Rödl theorem
• 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)