Fractional domatic number and minimum degree

-- Hugo Demaret (IPP)

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.

Category: seminars
Tags: Team seminar graphs