Séminaire Algorithmique : « Domination in subcubic graphs: swapping numbers », Paul Dorbec (GREYC, Caen)

In 1996, Bruce Reed worked on domination in cubic graphs, and came to the conclusion that 1/3 of the vertices should suffice in dominating connected cubic graphs. Things are not that simple as there are some counter-examples, but the problem still attracted attention (and gave birth to conjectures). In 2008, Lowenstein and Rautenbach made a relatively short paper (almost 9 pages) proving that the bound holds for graphs with girth 83. After coming back on any graph theoretical concept necessary to understand the proof, I will present how to swap this two numbers, i.e. how to prove that the bound holds for graph of girth 9 in a 83 pages paper…