Skip to Main content Skip to Navigation
Reports

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 , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Document type :
Reports
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070223
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 7:32:06 PM
Last modification on : Monday, October 12, 2020 - 10:30:21 AM
Long-term archiving on: : Sunday, April 4, 2010 - 8:39:28 PM

Identifiers

  • HAL Id : inria-00070223, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

323

Files downloads

235