Coloration des graphes de reines

Vasquez, Michel

doi:10.1016/j.crma.2005.11.022

Combinatoire

Coloration des graphes de reines

Présenté par : Gérard Huet

Vasquez, Michel ¹

¹ Centre de recherche LGI2P, École des mines d'Alès, parc scientifique Georges-Besse, 30035 Nîmes cedex 1, France

Comptes Rendus. Mathématique, Tome 342 (2006) no. 3, pp. 157-160.

Résumé
Abstract

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$ .

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 = 2 p$ or $n = 3 p$ , and $χ_{n} = n$ .

Reçu le : 2004-01-23
Accepté le : 2005-11-07
Publié le : 2006-01-06

DOI : 10.1016/j.crma.2005.11.022

Affiliations des auteurs :

Vasquez, Michel ¹

¹ 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, Tome 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/

Bibliographie
Cité par

[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

Cité par Sources :