Looseness of Planar Graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Graphs and Combinatorics Année : 2011

Looseness of Planar Graphs

Résumé

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.
Fichier principal
Vignette du fichier
CJK_11.pdf (132.83 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00634940 , version 1 (09-11-2011)

Identifiants

Citer

Július Czap, Stanislav Jendrol', František Kardoš, Jozef Miškuf. Looseness of Planar Graphs. Graphs and Combinatorics, 2011, 27 (1), pp.73-85. ⟨10.1007/s00373-010-0961-6⟩. ⟨inria-00634940⟩
129 Consultations
178 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More