19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Distinguishing colorings of $3$-connected planar graphs

Presented by Gašper FIJAVž
Type: Oral presentation
Track: Coloring of Graphs


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$.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors