On the chromatic number of circulant graphs |
| |
Authors: | Javier Barajas |
| |
Institution: | Dept. Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Barcelona, Spain |
| |
Abstract: | Given a set D of a cyclic group C, we study the chromatic number of the circulant graph G(C,D) whose vertex set is C, and there is an edge ij whenever i−j∈D∪−D. For a fixed set D={a,b,c:a<b<c} of positive integers, we compute the chromatic number of circulant graphs G(ZN,D) for all N≥4bc. We also show that, if there is a total order of D such that the greatest common divisors of the initial segments form a decreasing sequence, then the chromatic number of G(Z,D) is at most 4. In particular, the chromatic number of a circulant graph on ZN with respect to a minimum generating set D is at most 4. The results are based on the study of the so-called regular chromatic number, an easier parameter to compute. The paper also surveys known results on the chromatic number of circulant graphs. |
| |
Keywords: | Circulant graphs Chromatic number |
本文献已被 ScienceDirect 等数据库收录! |
|