Distinguishing colorings of 3-connected planar graphs with five colors
Gašper Fijavž, Seiya Negami, Terukazu Sano · Yokohama National University Repository (Yokohama National University) · 2015
A (proper) coloring of G with k colors is called a distinguishing k-coloring of G if there is no color-preserving automorphism of G other than the identity map.We shall prove that every 3-connected planar graph, with the exception of K 2,2,2 and C 6 +K 2 , admits a distinguishing 5-coloring which uses color 5 only for one vertex.By contrast, we shall present examples of 3-connected planar graphs that have distinguishing 4-colorings but no distinguishing 4-coloring with one color used only once.