Home > Timetable > Contribution details


Graphs with small distinguishing index


  • Monika PILSNIAK

Primary authors


\titleoftalk{Graphs with small distinguishing index} \speaker{{Monika} {Pil\'sniak}}
\university{Department of~Discrete Mathematics\AGH University, Krakow, Poland}


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


\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}