×

zbMATH — the first resource for mathematics

On a problem of P. Erdős. (English) Zbl 0612.05032
For \(\alpha\) real, \(0<\alpha <2\), and n an integer, let G(n,\(\alpha)\) be the graph whose vertices are the points of the unit sphere \(S^{n- 1}=\{x=(x_ 1,...,x_ n)\in {\mathbb{R}}^ n:\sum (x_ i)^ 2=1\}\), and which has an edge between two points if and only if they are a distance of \(\alpha\) apart. \(\chi\) (G(n,\(\alpha)\)) is the chromatic number of the graph G(n,\(\alpha)\), finite because \(S^{n-1}\) is a compact metric space. It is shown that for each \(\alpha\), \(\chi\) (G(n,\(\alpha)\))\(\to \infty\) as \(n\to \infty\). The proof uses known results on the chromatic number of Kneser graphs in a critical manner.
MSC:
05C15 Coloring of graphs and hypergraphs
05C99 Graph theory
PDF BibTeX XML Cite
Full Text: EuDML
References:
[1] B. BOLLOBÁS: Extremal Graph Theory. Academic Press, London-New York-San Francisco, 1978. · Zbl 0844.05054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.