Looseness of Planar Graphs

Július Czap 1 Stanislav Jendrol' 1 František Kardoš 2, 1 Jozef Miškuf 1
2 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 : A face of a vertex coloured plane graph is called loose if the number of colours used on its vertices is at least three. The looseness of a plane graph G is the minimum k such that any surjective k-colouring involves a loose face. In this paper we prove that the looseness of a connected plane graph G equals the maximum number of vertex disjoint cycles in the dual graph G increased by 2. We also show upper bounds on the looseness of graphs based on the number of vertices, the edge connectivity, and the girth of the dual graphs. These bounds improve the result of Negami for the looseness of plane triangulations. We also present infinite classes of graphs where the equalities are attained.
Type de document :
Article dans une revue
Graphs and Combinatorics, Springer Verlag, 2011, 27 (1), pp.73-85. <http://www.springerlink.com/content/q1112t64601q4x44/>. <10.1007/ s00373-010-0961-6>
Liste complète des métadonnées


https://hal.inria.fr/inria-00634940
Contributeur : František Kardoš <>
Soumis le : mercredi 9 novembre 2011 - 13:54:39
Dernière modification le : jeudi 27 mars 2014 - 10:58:08
Document(s) archivé(s) le : vendredi 10 février 2012 - 02:21:11

Fichier

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

Identifiants

Collections

Citation

Július Czap, Stanislav Jendrol', František Kardoš, Jozef Miškuf. Looseness of Planar Graphs. Graphs and Combinatorics, Springer Verlag, 2011, 27 (1), pp.73-85. <http://www.springerlink.com/content/q1112t64601q4x44/>. <10.1007/ s00373-010-0961-6>. <inria-00634940>

Partager

Métriques

Consultations de
la notice

159

Téléchargements du document

143