Choosability of the square of planar subcubic graphs with large girth

Frédéric Havet (1)

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications

We first show that the choose number of the square of a subcubic graph with maximum average degree less than 18/7 is at most 6. As a corollary, we get that the choose number of the square of a planar graph with girth at least 9 is at most 6. We then show that the choose number of the square of a subcubic planar graph with girth at least 13 is at most 5.

Mots clés: COLOURING; LIST COLOURING; PLANAR GRAPH; GIRTH

Domaines: Autre [cs.OH]

Frédéric Havet. Choosability of the square of planar subcubic graphs with large girth. [Research Report] RR-5800, INRIA. 2006, pp.17. ⟨inria-00070223⟩