Using region decomposition techniques for coloring problems

Speaker(s)

Marthe Bonamy

Affiliation

Université de Bordeaux

Date

Feb. 9, 2017, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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.

---