\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf Thomas W. Tucker}
%
%
\medskip
\noindent
%
%
{\bf Distinguishing Maps}
%
%
\vskip 5mm
\noindent
%
%
%
%
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.
\end{document}