Bounds for Distinguishing Invariants of Infinite Graphs

Abstract

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^{\prime }(G)$. We prove that $D^{\prime }(G)\le 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^{\prime }(G)$, for vertex and edge colourings, respectively. We show that ${\chi }_D(G)\le 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^{\prime }(G)\le {\chi }^{\prime }(G)+1$, where ${\chi }^{\prime }(G)$ is the chromatic index of $G$, and we prove a similar result ${\chi }_D^{\prime \prime }(G)\le {\chi }^{\prime \prime }(G)+1$ for proper total colourings. A number of conjectures are formulated.

Cited by in corpus (3)

• Number of Distinguishing Colorings and Partitions
• Distinguishing threshold of graphs
• Upper bounds for the list-distinguishing chromatic number