Abstract:
This paper is devoted to the classical Erdős–Hadwiger problem in combinatorial geometry. This problem of finding the minimum number of colours sufficient for colouring all points in the Euclidean space $\mathbb R^n$ such that points lying at distance 1 are painted distinct colours, is studied in one of the most important special cases relating to colouring of finite geometric graphs. Several new approaches to lower bounds for the chromatic numbers of such graphs are put forward. In a very broad class of cases these approaches enable one to obtain a considerable improvement over and generalization of all previously known results of this kind.
Fulltext:
PDF file (519 kB)
