Using region decomposition techniques for coloring problems

Prelegent(ci)

Marthe Bonamy

Afiliacja

Université de Bordeaux

Termin

9 lutego 2017 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

We consider the problem of coloring the square of a planar graph that has no small cycle. We prove a conjecture of Dvorak, Kral, Nejedly, and Skrekovski that planar graphs of girth at least five are square (∆ + 2)-colorable for large enough maximum degree ∆. This completes the characterization of which pairs of g and C yield that a planar graph with girth at least g is square (∆ + C)-colorable for large enough ∆. Interestingly, the proof can be seen as a transposition of the classical proof that planar Dominating Set admits a linear kernel when parameterized with the size of the solution.

---