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
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2009, 309, pp.3553--3563
Liste complète des métadonnées


https://hal.inria.fr/inria-00496423
Contributeur : Frederic Havet <>
Soumis le : dimanche 23 octobre 2016 - 16:33:34
Dernière modification le : mardi 25 octobre 2016 - 01:05:06

Fichier

girth.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00496423, version 1

Collections

Citation

Frédéric Havet. Choosability of the square of planar subcubic graphs with large girth. Discrete Mathematics, Elsevier, 2009, 309, pp.3553--3563. <inria-00496423>

Partager

Métriques

Consultations de
la notice

180

Téléchargements du document

56