The Codomatic Number of a Cubic Graph

Abstract

The maximum cardinality of a partition of the vertex set of a graph $G$ into dominating sets is the domatic number of $G$, denoted $d(G)$. The codomatic number of $G$ is the domatic number of its complement, written $d(\overline{G})$. We show that the codomatic number for any cubic graph $G$ of order $n$ is $n/2$, unless $G\in \{K_4,G_1\}$ where $G_1$ is obtained from $K_{2,3}\cup K_3$ by adding the edges of a 1-factor between $K_3$ and the larger partite set of $K_{2,3}$.