Combinatoire
Coloration des graphes de reines
[On the Queen graphs coloring problem]
Comptes Rendus. Mathématique, Volume 342 (2006) no. 3, pp. 157-160.

Until 2003 no chromatic numbers (χn) for the queen graphs were available for n>9 except where n is not a multiple of 2 or 3. In this research announcement we present an exact algorithm which provides coloring solutions for n=12,14,15,16,18,20,21,22,24,26,28 and 32 such as χn=n. Then we prove that there exists an infinite number of values for n such that n=2p or n=3p, and χn=n.

Jusqu'en 2003, le nombre chromatique des graphes de reines (χn) n'était pas connu pour des tailles de l'échiquier strictement supérieures à 9 et multiples de 2 ou de 3. Dans ce compte-rendu nous présentons une étude qui nous conduit dans un premier temps à trouver des colorations à n couleurs pour n=12,14,15,16,18,20,21,22,24,26,28 et 32. Nous montrons ensuite qu'il existe une infinité de valeurs de n divisibles par 2 ou 3 pour lesquelles χn=n.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2005.11.022
Vasquez, Michel 1

1 Centre de recherche LGI2P, École des mines d'Alès, parc scientifique Georges-Besse, 30035 Nîmes cedex 1, France
@article{CRMATH_2006__342_3_157_0,
     author = {Vasquez, Michel},
     title = {Coloration des graphes de reines},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {157--160},
     publisher = {Elsevier},
     volume = {342},
     number = {3},
     year = {2006},
     doi = {10.1016/j.crma.2005.11.022},
     language = {fr},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2005.11.022/}
}
TY  - JOUR
AU  - Vasquez, Michel
TI  - Coloration des graphes de reines
JO  - Comptes Rendus. Mathématique
PY  - 2006
SP  - 157
EP  - 160
VL  - 342
IS  - 3
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2005.11.022/
DO  - 10.1016/j.crma.2005.11.022
LA  - fr
ID  - CRMATH_2006__342_3_157_0
ER  - 
%0 Journal Article
%A Vasquez, Michel
%T Coloration des graphes de reines
%J Comptes Rendus. Mathématique
%D 2006
%P 157-160
%V 342
%N 3
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2005.11.022/
%R 10.1016/j.crma.2005.11.022
%G fr
%F CRMATH_2006__342_3_157_0
Vasquez, Michel. Coloration des graphes de reines. Comptes Rendus. Mathématique, Volume 342 (2006) no. 3, pp. 157-160. doi : 10.1016/j.crma.2005.11.022. http://www.numdam.org/articles/10.1016/j.crma.2005.11.022/

[1] B. Abramson, M.M. Yung, Construction through decomposition: a divide-and-conquer algorithm for the N-queens problem, in: Fall Joint Computer Conference, November 1986, pp. 620–628

[2] Caramia, M.; Dell'Olmo, P. Iterative coloring extension of a maximum clique, Naval Res. Logistic, Volume 48 (2001) no. 6, pp. 518-550

[3] http://www.research.att.com/projects/OEIS?Anum=A088202

[4] M. Chiarandini, T. Stützle, An application of iterated local search to graph coloring problem, in: A. Mehrotra, D.S. Johnson, M. Trick (Eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, Ithaca, NY, USA, September 2002, pp. 112–125

[5] J.P. Hamiez, Coloration de graphes et planification de rencontres sportives: heuristiques, algorithmes et analyses, Thèse de Doctorat, Université d'Angers, décembre 2002

[6] Mehrotra, A.; Trick, M.A. A column generation approach for graph coloring, INFORMS J. Comput., Volume 8 (1996) no. 4, pp. 344-354

Cited by Sources: