Distinguishing maps (Q540028)

Summary: The distinguishing number of a group \(A\) acting faithfully on a set \(X\), denoted \(D(A,X)\), is the least number of colors needed to color the elements of \(X\) so that no nonidentity element of \(A\) preserves the coloring. Given a map \(M\) (an embedding of a graph in a closed surface) with vertex set \(V\) and without loops or multiples edges, let \(D(M)= D(\Aut(M), V)\), where \(\Aut(M)\) is the automorphism group of \(M\); if \(M\) is orientable, define \(D^+(M)\) similarly, using only orientation-preserving automorphisms. It is immediate that \(D(M)\leq 4\) and \(D^+(M)\leq 3\). We use Russell and Sundaram's motion lemma to show that there are only finitely many maps \(M\) with \(D(M)> 2\). We show that if a group \(A\) of automorphisms of a graph \(G\) fixes no edges, then \(D(A,V)= 2\), with five exceptions. That result is used to find the four maps with \(D^+(M)= 3\). We also consider the distinguishing chromatic number \(\chi_D(M)\), where adjacent vertices get different colors. We show \(\chi_D(M)\leq\chi(M)+ 3\) with equality in only finitely many cases, where \(\chi(M)\) is the chromatic number of the graph underlying \(M\). We also show that \(\chi_D(M)\leq 6\) for planar maps, answering a question of Collins and Trenk. Finally, we discuss the implications for general group actions and give numerous problems for further study.