## Abstract

This note relates to bounds on the chromatic number χ(R^{n}) of the Eu- clidean space, which is the minimum number of colors needed to color all the points in R^{n} so that any two points at the distance 1 receive differ- ent colors. In [6] a sequence of graphs G_{n} in R^{n} was introduced showing that χ(R^{n}) ≥ χ(G_{n}) ≥ (1 + o(1))n^{2}/6 . For many years, this bound has been remaining the best known bound for the chromatic numbers of some low- dimensional spaces. Here we prove that χ(G_{n}) ~ n^{2}/6 and find an exact formula for the chromatic number in the case of n = 2^{k} and n = 2^{k} - 1. Keywords: chromatic number, independence number, distance graph.

Original language | English (US) |
---|---|

Pages (from-to) | 25-31 |

Number of pages | 7 |

Journal | Discussiones Mathematicae - Graph Theory |

Volume | 33 |

Issue number | 1 |

DOIs | |

State | Published - 2013 |

## Keywords

- Chromatic number
- Independence number
- Sistance graph

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics