Fractional domatic number and minimum degree
Time: 10:30 -- Location: LRI, 445
summary: We present a study of a graph parameter in graph theory, named the fractional domatic number.
A dominating set in a graph is a set of vertices such that every vertex outside the set is adjacent
to a vertex in the set. The domatic number of a graph is the maximum number of vertex disjoint dominating
sets that partition the vertex set of the graph.
We consider the fractional domatic number, which is the solution of the fractional relaxation of an integer
linear program that computes the domatic number. We study the extremal value of the fractional domatic number
of graphs of small minimum degree. Gadouleau, Harms, Mertzios, and Zamaraev recently proved that connected
graphs of minimum degree at least 2 have fractional domatic number more than 2 unless they are isomorphic
to a 4-cycle, and they conjectured that their fractional domatic number is at least 7/3 in that case.
We answer this conjecture in the affirmative.
This is a joint work with Quentin Chuet, Hugo Demaret, Hoang La and François Pirot.