Speaker
Monika Pilsniak
(AGH University, Krakow, Poland)
Description
\titleoftalk{Graphs with small distinguishing index}
\speaker{{Monika} {Pil\'sniak}}
\university{Department of~Discrete Mathematics\\AGH University, Krakow, Poland}
\email{pilsniak@agh.edu.pl}
\
\begin{abstract}The distinguishing index of~a graph $G$, denoted by $D'(G)$, is
the~least number of~colours in a general edge colouring of~$G$ not
preserved by any non-trivial automorphism. The definition of~$D'(G)$ was
introduced in 2015 in [3] as an analogue of the distinguishing number
defined by Albertson and Collins for vertex colouring, the concept of
which spawned more than a hundred of papers.
For connected graphs in general, we showed in [3] that $D'(G)\leq
\Delta(G)$ unless $G$ is $C_3$, $C_4$ or $C_5$. It was proved in [5],
that the equality $D'(G)= \Delta(G)$ holds only for cycles of~length at
least 6, for $K_4$, $K_{3,3}$ and for all symmetric and bisymmetric
trees, i.e., $D'(G)< \Delta(G)$ for all other connected graphs.
%\vspace{.3cm}
Interestingly, there are some wide classes of graphs with the distinguishing
index bounded by a small constant, e.g., traceable graphs, planar
graphs, claw-free graphs [5], Cartesian powers [2], and the Cartesian
product of denumerable graphs [1].
\vspace{0.3cm}
An analogous concept was also investigated for proper total colourings
in [4]. We
proved in particular that if $G$ is a~connected graph such that its
total chromatic index $\chi''(G)$ satisfies $\chi''(G)\geq\Delta(G) +2$,
then the total distinguishing chromatic index equals $\chi''(G)$.
\vspace{25pt}
\setlength{\parindent}{0cm}{\textbf{References:}
% Journal paper
[1] I. Broere, M. Pil\'sniak, {\it The distinguishing index of the Cartesian
product of countable graphs}, Ars Math. Contemp. 13 (2017) 15--21.
[2] A. Gorzkowska, R. Kalinowski, M. Pil\'sniak, {\it The distinguishing
index of the Cartesian product of graphs}, Ars Math. Contemp. 12 (2017)
77–-87.
[3] R.~Kalinowski and M.~Pil\'sniak, {\it Distinguishing graphs by edge
colourings}, {European J. Combin.} {45} (2015) 124--131.
[4] R. Kalinowski, M. Pil\'sniak, M. Wo\'zniak, {\it Distinguishing graphs by
total colourings}, {Ars Math. Contemp.}, (2016) 11:79–-89.
[5] M.~Pil\'sniak, {\it Improving Upper Bounds for the~Distinguishing Index},
{Ars Math. Contemp.} 13 (2017) 259--274.
}
%%% *****************
\end{abstract}
Primary author
Monika Pilsniak
(AGH University, Krakow, Poland)
