BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Bounds for the distinguishing index of finite graphs Kalinowski, Rafal


The distinguishing index $D'(G)$ of a graph $G$ is the least number of colours in an edge colouring that breaks all nontrivial automorphisms of $G$. This invariant is defined only for graphs with at most one isolated vertex and without $K_2$ as a component (we call them admissible graphs). The general upper bound for connected admissible graphs is $D'(G)\leq \Delta(G)$ except for small cycles $C_3,C_4,C_5$. Moreover, it was proved by the second author that the equality holds only for cycles of length at least six, symmetric and bisymmetric trees and for two small graphs $K_4,K_{3,3}$. Recently, we proved with Imrich and Woźniak that $$D'(G)\leq \left\lceil\sqrt{\Delta(G)}\right \rceil+1$$ for every connected graph of order at least seven and without pendant edges. There are classes of graphs with the distinguishing index at most two (perhaps with few known exceptions). For instance, traceable graphs, claw-free graphs, Cartesian powers of connected graphs, and 3-connected planar graphs (the latter result was recently proved by PilŠniak and Tucker). A number of open problems will be formulated. Coauthor: Monika PilŠniak

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International