On the queen graph coloring problem

• Main Author: Vasquez, Michel
• Other Authors: Laboratoire de Génie Informatique et Ingénierie de Production (LGI2P), IMT - MINES ALES (IMT - MINES ALES), Institut Mines-Télécom Paris (IMT)-Institut Mines-Télécom Paris (IMT)
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2006
• Subjects: Graph Coloring; Queen Graph; [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]; [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]; Iceland
• Online Access: https://hal.science/hal-00354882

International audience Queen graph coloring consists in covering a nxn chessboard with n2 colored queens such as 2 queens of same color do not attack each other. The minimum number of colors used to do so is the chromatic number Xn of the graph defined by the squares of the board and the queen move rule. An enumeration of the maximum stable sets reinforced by a clique filtering proves that X10=11, X12=12 and X14=14. Then a geometric heuristic shows that Xn=n for n = 15, 16, 18, 20, 21, 22, 24, 26, 28, 32. Finally linear congruence computations prove that there is an infinity of n multiples of 2 or 3 so that Xn=n.