Fractional domatic number and minimum degree

Quentin Chuet, Hugo Demaret, Hoang La, François Pirot · 2025

Read Fractional domatic number and minimum degree by Quentin Chuet, Hugo Demaret, Hoang La, François Pirot (2025) 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-2508-19617.txt.

Introduction

Chuet, Demaret, La, and Pirot study a relaxed form of the domatic number of a graph in twenty twenty-five. A domatic set touches every point of a graph, and the domatic number counts how many such sets can be packed without overlap. The relaxed form allows shares of points to count in fractions. They ask how low it can fall when each point has at least a set number of links.

For graphs where each point has at least two links, they prove a strong floor. Aside from eight odd graphs, the value stays at or above two and a half. They show the bound is best of its kind. Flat graphs with wide cycles get a bound near three.

Catalog record

CREATORQuentin Chuet, Hugo Demaret, Hoang La, François Pirot
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE103 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-19617

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fractional domatic number and minimum degree Quentin Chuet, Hugo Demaret, Hoang La, François Pirot Abstract The domatic number of a graph G G is the maximum number of pairwise disjoint dominating sets of G G . We are interested in the LP-relaxation of this parameter, which is called the fractional domatic number of G G . We study its extremal value in the class of graphs of minimum degree d d . The fractional domatic number of a graph of minimum degree d d is always at most d + 1 d+1 , and at least ( 1 − o ⁡ ( 1 ) ) ​ d / ln ⁡ d (1-o(1))\,d/\ln d as d → ∞ d\to\infty . This is asymptotically tight even within the class of split graphs. Our main result concerns the case d = 2 d=2 ; we show that, excluding 8 8 exceptional graphs, the fractional domatic number of every connected graph of minimum degree (at least) 2 2 is at least 5 / 2 5/2 . We also show that this bound cannot be improved if only finitely many graphs are excluded, even when restricting to bipartite graphs of girth at least 6 6 . This proves in a stronger sense a conjecture by Gadouleau, Harms, Mertzios, and Zamaraev (2024). This also extends and generalises results from McCuaig and Shepherd (1989), from Fujita, Kameda, and Yamashita (2000), and from Abbas, Egerstedt, Liu, Thomas, and Whalen (2016). Finally, we show that planar graphs of minimum degree at least 2 2 and girth at least g g have fractional domatic number at least 3 − O ⁡ ( 1 / g ) 3-O(1/g) as g → ∞ g\to\infty . 1 Introduction Given a graph G , a dominating set of G is a set X\subseteq V(G) such that N[X]=V(G) . Dominating sets are often used to model monitoring problems in networks. A classical problem in Graph Theory is to find the minimum size \gamma(G) of a dominating set of G , called the domination number of G [ 17 , 16 ] . A possible approach to this problem is to study a stronger parameter, the domatic number of G , denoted \dom(G) , which is the maximum number of pairwise disjoint dominating sets of G . Since dominating sets are stable through vertex addition, \dom(G) can equivalently be defined as the maximum size of a partition of V(G) into dominating sets. Such a partition is usually called a domatic partition of G , and can also be captured by the notion of dominating k -colouring of G , that is a mapping \varphi\colon V(G)\to[k] such that \varphi(N[v])=[k] for every vertex v\in V(G) — in other words, every closed neighbourhood spans all the colours in \varphi . Then \dom(G) is the maximum k such that G has a dominating k -colouring. A straightforward application of the Pigeonhole Principle yields that the minimum colour class in a dominating k -colouring of G has size at most |V(G)|/k , hence \gamma(G)\leq\lvert V(G)\rvert/\dom(G) . As a consequence, any lower bound on \dom(G) yields an upper bound on \gamma(G) . For instance, Matheson and Tarjan [ 16 ] proved that every n -vertex triangulated disc (i.e. a 2 -connected planar graph, all internal faces of which are triangles) has domination number at most n/3 , by showing that its domatic number is at least 3 . A parallel can be made with independent sets and the chromatic number of graphs. Remarkably, there is no known proof for the fact that every n -vertex planar graph contains an independent set of size at least n/4 that does not rely on the 4 -Colour Theorem . We are interested in the LP-relaxation of the domatic number, called the fractional domatic number , which provides a tighter bound on the domination number. This parameter was first formally introduced in [ 22 ] , although some related notions already appeared in [ 9 ] . It has many equivalent definitions; we mention some of them hereafter. Linear Programming We denote \mathcal{D}(G) the collection of dominating sets of a given graph G . Then the fractional domatic number of G , denoted \fdom(G) , is the solution to the following linear program: \displaystyle\mbox{Maximise} \displaystyle\sum_{D\in\mathcal{D}(G)}x_{D}, (1) \displaystyle\mbox{Subject to} \displaystyle\left\{\begin{array}[]{rl}\displaystyle\sum_{\begin{subarray}{c}D\in\mathcal{D}(G)\\ v\in D\end{subarray}}x_{D}\leq 1&\mbox{for all $v\in V(G)$;}\\ x_{D}\geq 0&\mbox{for all $D\in\mathcal{D}(G)$.}\end{array}\right. Probability distribution If (x_{D})_{D\in\mathcal{D}(G)} yields a solution to ( 1 ), then observe that a renormalisation of the weights x_{D} yields a probability distribution over \mathcal{D}(G) , in such a way that a random dominating set \mathbf{D} drawn according to that distribution satisfies \mathbb{P}\left[v\in\mathbf{D}\right]\leq\frac{1}{\fdom(G)} for every vertex v\in V(G) . So the fractional domatic number of G can alternatively be defined as \fdom(G)=\max\left\{\frac{1}{p}:\begin{array}[]{c}\mbox{there is a random dominating set $\mathbf{D}$ of $G$ such that}\\ \mathbb{P}\left[v\in\mathbf{D}\right]\leq p\mbox{ for every vertex $v\in V(G)$.}\end{array}\right\}. (2) Dominating sets with bounded overlaps The theory of Linear Programming tells us that the solution to ( 1 ) is a rational number. So there is an integer q such that q\cdot x_{D} is an integer for every D\in\mathcal{D}(G) . We construct a multiset \mathcal{F} of dominating sets of G by adding q\cdot x_{D} copies of D to \mathcal{F} for every D\in\mathcal{D}(G) . By doing so, every vertex v\in V(G) appears in at most q dominating sets of \mathcal{F} ; we call that number of occurrences the multiplicity of v in \mathcal{F} . Letting m(\mathcal{F}) be the maximum multiplicity of a vertex in \mathcal{F} , we obtain that \fdom(G)=\max\,\frac{\mathcal{F}}{m(\mathcal{F})}, (3) where the maximum is taken over every multiset \mathcal{F} of dominating sets of G . Dominating (p:q) -colourings If a given vertex v\in V(G) appears in fewer than m(\mathcal{F}) dominating sets of \mathcal{F} , we may add it to some extra ones so that its multiplicity in \mathcal{F} is exactly m(\mathcal{F}) . This ensures that the maximum in ( 3 ) is attained by a multiset \mathcal{F} in which every vertex has equal multiplicity. We represent this with a dominating (p:q) -colouring of G , that is a mapping \varphi\colon V(G)\to\binom{[p]}{q} such that \bigcup_{u\in N[v]}\varphi(u)=[p] for every vertex v\in V(G) — in other words, every closed neighbourhood spans all the colours in \varphi . This is illustrated in Figure 1 . When p and q are not explicit, we say that \varphi is a fractional dominating colouring of G . Then we have \fdom(G)=\max\left\{\frac{p}{q}:\mbox{there is a dominating $(p:q)$-colouring of $G$.}\right\}. (4) 1,6,7 2,4,5 1,2,3 3,6,7 1,4,5 (a) K_{2,3} . 1,2,3 4,5,6 7,1,2 3,4,5 6,7,1 2,3,4 5,6,7 (b) C_{7} . 3,5,6 1,2,7 3,4,6 1,4,5 2,5,7 1,3,6 2,4,7 (c) Two C_{4} ’s with a common vertex. Figure 1 : Examples of dominating (7:3) -colourings. Each number represents a dominating set. Domatic number and chromatic number The study of the domatic number is analogous to that of the chromatic number. The chromatic number of a graph G , denoted \chi(G) , is the minimum size of a partition of V(G) into independent sets. The fractional chromatic number \chi_{f}(G) corresponds to the LP-relaxation of the chromatic number. As for \fdom(G) , there are many equivalent definitions of \chi_{f}(G) ; let us mention that related to colourings. Given integers p\geq q , a proper (p:q) -colouring of G is a mapping

Read the complete text