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

CREATORQuentin Chuet, Selma Djelloul, Hoang La, François Pirot, Hossein Zaredehabadi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text