| Summary: | 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.
|
|---|