Improved bounds on the domatic numbers of queens graphs

The queens graph Qn, for any positive integer n, has the n 2 squares of the n n chessboard as its vertices with two vertices adjacent if and only if they are on the same row, column, or diagonal of the board.Recently, Hedetniemi et al. [Congr.Numer.235 (2024) 5-21] determined exact values or provided bounds for the domatic, idomatic, and total domatic number of Qn for n up to 9. For an undirected graph G, these numbers are denoted by dom(G), idom(G), and tdom(G), respectively, and defined as the maximum order k for which a partition {V1, V2, . . ., V k } of V (G) into (dominating, independent dominating, total dominating) sets exists.In this paper, using a computational approach based on SAT solvers, some of their open questions are settled precisely, and improvements upon their bounds are obtained.In particular, for the domatic number, it is shown that dom(Q7) = 11, dom(Q9) = 13, dom(Q10) = 16, dom(Q11) {18, 19, 20}, and dom(Q12) {20, 21}.For the idomatic number, it is shown that idom(Q9) = 14, idom(Q10) {15, 16}, idom(Q11) = 17, and idom(Q12) {18, 19, 20}.Finally, for the total domatic number, it is established that tdom(Q9) = 14, tdom(Q10) {15, 16}, tdom(Q11) {16, 17}, and tdom(Q12) {18, 19, 20}.