Bounds for distinguishing invariants of infinite graphs

Wilfried Imrich¹ ; Rafał Kalinowski² ; Monika Pilśniak² ; Mohammad Hadi Shekarriz³

¹University of Leoben
²AGH University
³Ferdowsi University of Mashhad

The electronic journal of combinatorics, Tome 24 (2017) no. 3

Résumé

We consider infinite graphs. The distinguishing number $D(G)$ of a graph $G$ is the minimum number of colours in a vertex colouring of $G$ that is preserved only by the trivial automorphism. An analogous invariant for edge colourings is called the distinguishing index, denoted by $D'(G)$. We prove that $D'(G)\leq D(G)+1$. For proper colourings, we study relevant invariants called the distinguishing chromatic number $\chi_D(G)$, and the distinguishing chromatic index $\chi'_D(G)$, for vertex and edge colourings, respectively. We show that $\chi_D(G)\leq 2\Delta(G)-1$ for graphs with a finite maximum degree $\Delta(G)$, and we obtain substantially lower bounds for some classes of graphs with infinite motion. We also show that $\chi'_D(G)\leq \chi'(G)+1$, where $\chi'(G)$ is the chromatic index of $G$, and we prove a similar result $\chi''_D(G)\leq \chi''(G)+1$ for proper total colourings. A number of conjectures are formulated.

Détail

DOI : 10.37236/6362

Classification : 05C15, 05C25, 05C63
Mots-clés : symmetry breaking, distinguishing colouring, infinite motion conjecture