PhD successfully defended on February the 9th, 2015.


Maria Chudnovsky
Roland Ducournau
Cyril Gavoille
Frédéric Havet
Dan Kráľ
Benjamin Lévêque
Alexandre Pinlou
(Professor, Columbia university)
(Professor, UM2)
(Professor, Université de Bordeaux)
(DR CNRS, I3S Sophia-Antipolis)
(Professor, Warwick University)
(MCF LIRMM, hab.)
Reviewer (absent)

Manuscript summary:

This PhD thesis follows three main axes. First, we give an illustrated overview of the discharging tools that are used for this work: nice methods that we apply, and handy tricks that we develop. We try in particular to give an intuition of global discharging arguments. For that purpose, we consider an exotic kind of coloring, namely "adjacent vertex distinguishing edge coloring", where we seek a proper edge coloring with the extra property that no two neighbors are incident with the same set of colors. Beside its own history, the interesting characteristic of that coloring is that it behaves nicely with regard to all desired methods and tools, which makes it a natural candidate for illustration.

We then discuss two special cases: list edge coloring and square coloring. In the realm of list edge coloring, we most notably prove that the weak List Coloring Conjecture is true for planar graphs of maximum degree 8 (i.e. that they are edge 9-choosable), thus improving over a result of Borodin from 1990. Though the full proof is 24 pages long, compared to a lean two to solve the case of maximum degree at least 9, it rests upon a single decisive idea, which lies in a recoloring argument to get around reducibility problems.

In the case of square coloring, the goal is to color the square of the graph, or, equivalently, to 2-distance color the graph: we look for a proper coloring of a graph that satisfies the additional condition that the same color cannot be assigned to two vertices with a common neighbor. We are mainly interested in sufficient conditions on the sparsity of a graph for it to be colorable with the minimum number of colors or close to it. We generalize most of the existing results on planar graphs with given girth by supplanting the condition on the girth with a more general condition on the maximum average degree (mad) and dropping the planarity hypothesis.

Also, the fact that the girth is a discrete parameter contrary to the mad means that we can obtain more refined information with mad. In particular, it was known that the square of planar graphs with girth at least 7 and sufficiently large maximum degree can be colored with the minimum number of colors, while this can be false for squares of planar graphs with girth 6. It holds that all planar graphs with girth at least 6 have mad less than 3. With a global discharging argument, we can actually prove that planarity is, again, unnecessary, and that this property is in fact true as soon as the maximum degree is sufficiently larger than a function of the gap between 3 and the mad.

The slides are available here. The manuscript will soon follow.

Back to Homepage