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

Gašper Fijavž, Seiya Negami, Terukazu Sano


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 K2,2,2 and C6 + overline(K)2 and that every 3-connected bipartite planar graph is 3-distinguishing colorable except Q3 and R(Q3).


planar graphs, distinguishing number, distinguishing chromatic number

Full Text:


DOI: https://doi.org/10.26493/1855-3974.199.a0e

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications