A Domatic Analogue of χ \chi -Bounded Graph Classes and the Gyárfás–Sumner Conjecture
Quentin Chuet, Selma Djelloul, Hoang La, François Pirot, Hossein Zaredehabadi · 2026
Read A Domatic Analogue of χ \chi -Bounded Graph Classes and the Gyárfás–Sumner Conjecture by Quentin Chuet, Selma Djelloul, Hoang La, François Pirot, Hossein Zaredehabadi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-02030.txt.
Introduction
Chuet and co-authors define a domatic analogue of chi-bounded graph classes. A dominating set touches every vertex of a graph. The domatic number counts a largest such partition. Vertices are split into the most dominating sets possible. Minimum degree bounds that number from above.
A class is DOM-bounded if a growing function lower-bounds it. The bound depends on minimum degree alone. The notion mirrors chi-boundedness for chromatic number. A conjecture analogous to Gyárfás-Sumner is proposed. It covers classes forbidding a fixed induced subgraph. Connected forbidden graphs are the case of interest. The paper sets up the framework and conjecture. It invites work on domatic analogues of coloring theory.
Catalog record
| CREATOR | Quentin Chuet, Selma Djelloul, Hoang La, François Pirot, Hossein Zaredehabadi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.02030
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Domatic Analogue of χ \chi -Bounded Graph Classes and the Gyárfás–Sumner Conjecture Quentin Chuet, Selma Djelloul, Hoang La, François Pirot, Hossein Zaredehabadi Abstract Given a graph G G , a dominating set is a subset X ⊆ V ( G ) X\subseteq V(G) such that N [ X ] = V ( G ) N[X]=V(G) . The domatic number of G G , denoted DOM ( G ) \dom(G) , is the maximum size of a partition of V ( G ) 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 DOM ( G ) ≤ δ ( G ) + 1 \dom(G)\leq\delta(G)+1 where δ ( G ) \delta(G) is the minimum degree of G G . Therefore, as an analogue of the notion of χ \chi -bounded graph classes, we say that a class of graphs 𝒢 \mathscr{G} is DOM-bounded if there exists a positive unbounded function f 𝒢 f_{\mathscr{G}} such that for every G ∈ 𝒢 G\in\mathscr{G} , we have DOM ( G ) ≥ f 𝒢 ( δ ( G ) ) \dom(G)\geq f_{\mathscr{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 H , the class of H H -free graphs is DOM-bounded if and only if H H is a tree of diameter at most 3 3 . We reduce the case of disconnected graphs to the connected setting and show that the conditions on H H are necessary. We show that star-free graphs of minimum degree at least δ \delta have domatic number Ω ( δ / log δ ) \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 P_{4} -free graphs (i.e. cographs) of minimum degree δ \delta have domatic number at least 1 + δ 2 1+\frac{\delta}{2} , which is best possible. 1 Introduction Let G be a graph and k an integer. Given a k -colouring \phi\colon V(G)\to[k] , we say that \phi is dominating if \phi(N[v])=[k] for every vertex v\in V(G) . Equivalently, the colour classes of \phi form a domatic partition of G , that is, a partition of V(G) into dominating sets (recall that a subset X\subseteq V(G) is dominating if N[X]=V(G) ). The domatic number \dom(G) of G is the maximum k such that a dominating k -colouring of G exists. A standard upper bound is \dom(G)\leq\delta(G)+1 , where \delta(G) denotes the minimum degree of G . If equality holds, then G is said to be domatically full . The largest known class of domatically full graphs is that of strongly chordal graphs [ 5 ] . The equality between the chromatic number and the clique in perfect graphs, and more generally, their functional equivalence in \chi -bounded classes naturally parallels the relationship between the domatic number and the minimum degree in domatically full graphs, and more broadly, in DOM-bounded classes which we define as follows. Given a class of graphs \mathscr{G} , we say that \mathscr{G} is DOM-bounded if there exists a positive unbounded function f_{\mathscr{G}} such that \dom(G)\geq f_{\mathscr{G}}(\delta(G)) for every graph G\in\mathscr{G} . We say that f_{\mathscr{G}} is a DOM-binding function of \mathscr{G} , and if there is no graph G\in\mathscr{G} such that \dom(G)>f_{\mathscr{G}}(\delta(G)) , we further say that f_{\mathscr{G}} is optimal . This condition is trivially satisfied when \mathscr{G} has bounded minimum degree; consequently, we restrict our attention to classes with arbitrarily large minimum degree. In particular, non-trivial minor-closed classes of graphs are not relevant with respect to DOM-boundedness, as every H -minor-free graph (for a fixed t -vertex graph H ) is O(t\sqrt{\log t}) -degenerate [ 10 ] . Zelinka [ 17 ] proved that the class of all graphs is not DOM-bounded by constructing graphs with domatic number 2 and arbitrarily large minimum degree (see Section 3 ). By modifying Zelinka’s construction (which is bipartite), we obtain split graphs and high-girth graphs with the same property. Hence, bipartite graphs, split graphs, and graphs of high girth are not DOM-bounded. The objective of this paper is to identify structural constraints that guarantee DOM-boundedness. We turn our attention to the classes of graphs with forbidden sub-structures. Forbidden subgraphs Consider the class \mathscr{G} of graphs that do not contain a fixed graph H as a subgraph. If H contains a cycle of length \ell , then \mathscr{G} contains the class of graphs of girth greater than \ell , which is not DOM-bounded. Otherwise, H is a forest, and every graph in \mathscr{G} is (|V(H)|-2) -degenerate, and therefore has bounded minimum degree. Thus, forbidding a subgraph does not provide a meaningful structural constraint with respect to DOM-boundedness. Forbidden induced subgraphs A graph G is H -free if it does not contain H as an induced subgraph; we denote by \forb(H) the class of H -free graphs. More generally, given a family \mathcal{F} of graphs, we say that G is \mathcal{F} -free if it is H -free for every H\in\mathcal{F} , and we denote by \forb(\mathcal{F}) the corresponding class. Our goal is to characterise the graphs H for which \forb(H) is DOM-bounded. The analogous problem for \chi -boundedness is the Gyárfás–Sumner Conjecture. Conjecture 1 (Gyárfás, 1975 [ 9 ] ; Sumner, 1981 [ 16 ] ) . For every graph H , \forb(H) is \chi -bounded if and only if H is a forest. As in the case of forbidding H as a (non-induced) subgraph, if H contains a cycle of length \ell , then \forb(H) contains the class of graphs of girth greater than \ell , which is not DOM-bounded. If H is connected and has diameter at least 4 , then it contains an induced copy of P_{5} . Hence, \forb(H) contains the class of split graphs (which are P_{5} -free) and is not DOM-bounded. If H has at least two connected components of size at least 2 , then \forb(H) contains \forb(2K_{2}) , which in turn contains the class of split graphs. Hence, \forb(H) is not DOM-bounded. Consequently, when H is disconnected, \forb(H) can be DOM-bounded only if there exist a connected graph H_{0} and a positive integer k such that H is the disjoint union of H_{0} and k isolated vertices, and \forb(H_{0}) is DOM-bounded (since \forb(H_{0})\subseteq\forb(H) ). We prove that the converse also holds. Theorem 2 . Let H be a disconnected graph. Then \forb(H) is DOM-bounded if and only if H has at most one connected component H_{0} of order at least 2 , and \forb(H_{0}) is DOM-bounded. The remaining graphs to consider are trees of diameter at most 3 . We conjecture that all such graphs yield DOM-bounded classes. Conjecture 3 . For every connected graph H , \forb(H) is DOM-bounded if and only if H is a tree of diameter at most 3 . A