may be interpreted as a Latin square: it describes a way of filling the rows and columns of an grid with different values in such a way that the same value does not appear twice in any row or column. Although finding an optimal coloring of a rook's graph is straightforward, it is NP-complete to determine whether a partial coloring can be extended to a coloring of the whole graph (this problem is called precoloring extension). Equivalently, it is NP-complete to determine whether a partial Latin square can be completed to a full Latin square. Independence An independent set in a rook's graph is a set of vertices, no two of which belong to the same row or column of the graph; in chess terms, it corresponds to a placement of rooks no two of which attack each other. Perfect graphs may also be described as the graphs in which, in every induced subgraph, the size of the largest independent set is equal to the number of cliques in a partition of the graph's vertices into a minimum number of cliques. In a rook's graph, the sets of rows or the sets of columns (whichever has fewer sets) form such an optimal partition. The size of the largest independent set in the graph is therefore . Every color class in every optimal coloring of a rook's graph is a maximum independent set. Rook's graphs are well-covered graphs: every independent set in a rook's graph can be extended to a maximum independent set, and every maximal independent set in a rook's graph has the same size, . Domination The domination number of a graph is the minimum cardinality among all dominating sets. On the rook's graph a set of vertices is a dominating set if and only if their corresponding squares either occupy, or are a rook's move away from, all squares on the board. For the board the domination number is . On the rook's graph a -dominating set is a set of vertices whose corresponding squares attack all other squares (via a rook's move) at least times. A -tuple dominating set on the rook's graph is a set of vertices whose corresponding squares attack all other squares at least times and are themselves attacked at least times. The minimum cardinality among all -dominating and -tuple dominating sets are the -domination number and the -tuple domination number, respectively. On the