Gašper Fijavž: Distingushing number of bipartite planar graphs

A graph G is called d-distinguishing colorable if there is a d-coloring of G so that no automorphism (except the identity map) of G preserves vertex colors. In one of the previous seminars we have proven that every 3-connected planar except K_2,2,2 and C_6*2K_1 is 5-distinguishing colorable. We will show that every 3-connected bipartite planar graph is 3-distinguishing colorable with the exception of cube and its radial graph.

This is joint work with Seiya Negami and Terukazu Sano.