Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers

DOI10.1070/IM2014v078n01ABEH002680zbMath1287.05029OpenAlexW2322848408MaRDI QIDQ5412823

Publication date: 28 April 2014

Published in: Izvestiya: Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1070/im2014v078n01abeh002680

zbMATH Keywords

chromatic number distance graph clique number Nelson problem

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Ramsey theory (05D10)

Related Items (11)

Lower bounds for the chromatic numbers of distance graphs with large girth ⋮ On the chromatic numbers of rational spaces ⋮ Erdős-Ko-Rado theorem for \(\{0,\pm 1\}\)-vectors ⋮ Chromatic numbers of distance graphs with several forbidden distances and without cliques of a given size ⋮ Intersection theorems for \((- 1, 0, 1)\)-vectors ⋮ The chromatic number of space with forbidden regular simplex ⋮ An exact result for \((0, \pm 1)\)-vectors ⋮ Distance graphs with large chromatic number and without cliques of given size in the rational space ⋮ Chromatic numbers of distance graphs without short odd cycles in rational spaces ⋮ Two problems on matchings in set families -- in the footsteps of Erdős and Kleitman ⋮ Counterexamples to Borsuk's conjecture with large girth

This page was built for publication: Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers