Sur le nombre domatique du n-cube et une conjecture de Zelinka. (On the domatic number of the n-cube and a conjecture of Zelinka) (Q1100480): Difference between revisions

The domatic number of a graph G is the maximum number of classes of a partition of the vertex set of G into dominating sets. The reviewer has proved that for the graphs of the cubes of dimensions \(2^ p-1\) and \(2^ p\) the domatic number is equal to \(2^ p\) for any positive integer p. He has proposed the conjecture that the domatic number of the graph of the cube of dimension n, where n is not of the form \(2^ p-1\), is equal to n. The author disproves this conjecture by showing that the graph of the cube of dimension 5 has the domatic number equal to 4. He proposes a weakened form of the conjecture, namely the conjecture that the domatic number of the graph of the cube and the dimension of the cube are asymptotically equal.