Choosability of the square of planar subcubic graphs with large girth |
| |
Authors: | F Havet |
| |
Institution: | Projet Mascotte, CNRS/UNSA/INRIA, INRIA Sophia-Antipolis, 2004 route des Lucioles BP 93, 06902 Sophia-Antipolis Cedex, France |
| |
Abstract: | We show that the choice 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 choice number of the square of a subcubic planar graph with girth at least 9 is at most 6. We then show that the choice number of the square of a subcubic planar graph with girth at least 13 is at most 5. |
| |
Keywords: | List colouring Square of a graph Bounded density Planar graph |
本文献已被 ScienceDirect 等数据库收录! |
|