19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Distinguishing colorings of $3$-connected planar graphs
Presented by Gašper FIJAVž
Type: Oral presentation
Track: Coloring of Graphs
Content
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$.
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled
Co-authors
- Seiya NEGAMI Yokohama National University
- Sano TERUKAZU Yokohama National University