HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 7:32:06 PM
Last modification on : Friday, February 4, 2022 - 3:20:09 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

95

Files downloads

120