3-Connected planar graphs are 5-distinguishing colorable with two exceptions

Abstract

A graph G is said to be d-distinguishing colorable if there is a d-coloring of G such that no automorphism of G except the identity map preserves colors. We shall prove that every 3-connected planar graph is 5-distinguishing colorable except K_2,2,2 and C₆ + overline(K)₂ and that every 3-connected bipartite planar graph is 3-distinguishing colorable except Q₃ and R(Q₃).