| |
|
|
Abstract: A face of a vertex coloured plane graph is called {\em loose} if the number of colours used on its vertices is at least three. A $k$-colouring of a graph $G$ is called the {\em loose $k$-colouring} if it involves a loose face. The {\em looseness} of a plane graph $G$, $ls(G)$, is the minimum $k$ such that any surjective $k$-colouring is a loose $k$-colouring of $G$. In this paper we prove that the looseness of a connected plane graph $G$ equals $2$ plus the maximum number of vertex disjoint cycles in the dual graph $G^*$. We also show upper bounds on the looseness of graphs based on the edge connectivity, the girth of the dual graphs and other basic graph invariants. Moreover, we present infinite classes of graphs where these equalities are attained. Contact the authors: julius.czap@upjs.sk, stanislav.jendrol@upjs.sk, frantisek.kardos@upjs.sk, jozef.miskuf@upjs.sk Download PDF version of the preprint. |