Edge looseness of plane graphs - Czap, Július (Ars mathematica contemporanea, 2015)
A face of an edge colored plane graph is called e-loose if the number of colors used on its edges is at least three. The e-looseness of a plane graph ?$G$? is the minimum positive integer ?$k$? such that any edge coloring of ?$G$? with ?$k$? colors involves an e-loose face. In this paper we determine tight lower and upper bounds for the e-looseness of connected plane graphs. These bounds are expressed by linear polynomials of the number of faces.
Keywords: barvanje povezav; edge coloring; plane graph; ravninski graf