Some structural properties of planar graphs and their applications to 3-choosability

Min Chen 1 Mickaël Montassier 2, 1 André Raspaud 1
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In this article, we consider planar graphs in which each vertex is not incident to some cycles of given lengths, but all vertices can have different restrictions. This generalizes the approach based on forbidden cycles which corresponds to the case where all vertices have the same restrictions on the incident cycles. We prove that a planar graph G is 3-choosable if it is satisfied one of the following conditions: (1) G has no cycles of length 4 or 9 and no 6-cycle is adjacent to a 3-cycle. Moreover, for each vertex x , there exists an integer i x ∈ 5 , 7 , 8 such that x is not incident to cycles of length i x . (2) G has no cycles of length 4, 7, or 9, and for each vertex x , there exists an integer i x ∈ 5 , 6 , 8 such that x is not incident to cycles of length i x . This result generalizes several previously published results (Zhang and Wu, 2005 [12], Chen et al., 2008 [3], Shen and Wang, 2007 [6], Zhang and Wu, 2004 [13], Shen et al., 2011 [7]).
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2012, 312 (2), pp.362-373. 〈10.1016/j.disc.2011.09.028〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00782828
Contributeur : Mickael Montassier <>
Soumis le : mercredi 30 janvier 2013 - 16:32:54
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Citation

Min Chen, Mickaël Montassier, André Raspaud. Some structural properties of planar graphs and their applications to 3-choosability. Discrete Mathematics, Elsevier, 2012, 312 (2), pp.362-373. 〈10.1016/j.disc.2011.09.028〉. 〈lirmm-00782828〉

Partager

Métriques

Consultations de la notice

158