A Domatic Analogue of $\chi$-Bounded Graph Classes and the Gyárfás-Sumner Conjecture

Abstract

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 $\mathrm{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 $\mathrm{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 $\mathcal{G}$ is \emph{DOM-bounded} if there exists a positive unbounded function $f_{\mathcal{G}}$ such that for every $G\in \mathcal{G}$, we have $\mathrm{dom}(G)\ge f_{\mathcal{G}}(\delta (G))$. We propose the following conjecture for graphs forbidding a fixed induced subgraph, analogous to the Gyárfás--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.