Coloration des graphes de reines

Résumé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. Pour citer cet article : M. Vasquez, C. R. Acad. Sci. Paris, Ser. I 342 (2006).

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. To cite this article: M. Vasquez, C. R. Acad. Sci. Paris, Ser. I 342 (2006).