Cyclic, diagonal and facial colorings

AbstractIn an l-facial coloring, any two different vertices that lie on the same face and are at distance at most l on that face receive distinct colors. The concept of facial colorings extends the well-known concept of cyclic colorings. We prove that 18l5+2 colors suffice for an l-facial coloring of a plane graph. For l=2,3 and 4, the upper bounds of 8, 12 and 15 colors are shown. We conjecture that each plane graph has an l-facial coloring with at most 3l+1 colors. Our results on facial colorings are used to decrease to 16 the upper bound on the number of colors needed for 1-diagonal colorings of plane quadrangulations