Distinguishing maps

Thomas W. Tucker

The electronic journal of combinatorics, Tome 18 (2011) no. 1

Résumé

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({\rm Aut}(M),V)$, where ${\rm 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.

Détail

DOI : 10.37236/537

Classification : 05E18, 05C10