A Domatic Analogue of chi-Bounded Graph Classes and the Gy\'{a}rf\'{a}s-Sumner Conjecture

Given a graph $G$, a dominating set is a subset $X\subseteq V(G)$ such that $N[X]=V(G)$. The \emph{domatic number} of $G$, denoted ${\rm dom}(G)$, is the maximum size of a partition of $V(G)$ into dominating sets. In analogy with the lower bound of the chromatic number by the clique number, the domatic number satisfies the upper bound ${\rm dom}(G)\le \delta(G)+1$ where $\delta(G)$ is the minimum degree of $G$. Therefore, as an analogue of the notion of $\chi$-bounded graph classes, we say that a class of graphs $\mathscr{G}$ is \emph{DOM-bounded} if there exists a positive unbounded function $f_{\mathscr{G}}$ such that for every $G\in \mathscr{G}$, we have ${\rm dom}(G) \ge f_{\mathscr{G}}(\delta(G))$. We propose the following conjecture for graphs forbidding a fixed induced subgraph, analogous to the Gy\'arf\'as--Sumner Conjecture for $\chi$-bounded graph classes: for every connected graph $H$, the class of $H$-free graphs is DOM-bounded if and only if $H$ is a tree of diameter at most $3$. We reduce the case of disconnected graphs to the connected setting and show that the conditions on $H$ are necessary. We show that star-free graphs of minimum degree at least $\delta$ have domatic number $\Omega(\delta /\log \delta)$, which is best possible up to a constant factor. We also identify a subclass of star-free graphs for which the domatic number is linear in $\delta$: line graphs of bounded rank hypergraphs. In support of our conjecture in the case of double stars, we prove that $P_4$-free graphs (i.e. cographs) of minimum degree $\delta$ have domatic number at least $1 + \frac{\delta}{2}$, which is best possible.