2011-06-19T16:00:00 2011-06-25T16:00:00 2010-08-16T15:35:50 2013-05-25T06:16:49 Europe/Ljubljana Prof. Prof. Prof. Prof. 169 false [["minutes", "Minutes"], ["paper", "Paper"], ["poster", "Poster"], ["slides", "Slides"]] Coloring of Graphs 0 Oral presentation Distinguishing colorings of $3$-connected planar graphs University of Ljubljana gasper.fijavz@fri.uni-lj.si University of Ljubljana gasper.fijavz@fri.uni-lj.si Yokohama National University negami@edhs.ynu.ac.jp Yokohama National University d08tc004@ynu.ac.jp Bled, Slovenia
We call a graph $G$ \emph{$d$-distinguishing colorable} if there exists a $d$-coloring of $G$ such that no automorphism of $G$ except the identity preserves colors. \emph{Distinguishing chromatic number} of a graph $G$, denoted by $\chi_D(G)$, is the smallest integer $d$ so that $G$ is $d$-distinguishing colorable. Distinguishing colorings were introduced by Collins and Trenk in 2006, building upon an earlier concept of distinguishing labelling of graphs intorduced by Albertson and Collins in 1996. Our focus lies in the class of 3-connected planar graphs. It is not difficult to see that $\chi_D(K_{2,n})=2+n$, but in the case of 3-connected planar graphs the distinguishing chromatic number is bounded. Let $G$ be a $3$-connected planar graph. We show that: \begin{enumerate} \item[(i)] $\chi_D(K_{2,2,2})=\chi_D(C_6 * \overline{K_2})=6$, and for $n\ne 4,6$ we have $\chi_D(C_n * \overline{K_2}) =5$. Similarly $\chi_D(Q_3)=\chi_D(R(Q_3))=4$, where $R(Q_3))$ denotes the radial graph (or vertex-face graph) of the cube $Q_3$. \item[(ii)] Apart from the exceptions in (i) the inequality $\chi_D(G) \le \chi(G) +1$ holds. \end{enumerate} Assuming $\chi_D(G)=\chi(G)+1$ we would like to use the additional color on as few vertices as possible. It is indeed possible to use the additional color 5 on a single vertex in order to produce a $5$-distinguishing coloring of a $4$-chromatic $3$-connected planar graph $G$.