Bounds for Distinguishing Invariants of Infinite Graphs

Autor: Imrich, Wilfried, Kalinowski, Rafał, Pilśniak, Monika, Shekarriz, Mohammad H.
Rok vydání: 2019
Předmět:
Zdroj: The electronic journal of combinatorics 24(3) (2017), #P3.6
Druh dokumentu: Working Paper
DOI: 10.37236/6362
Popis: 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.
Databáze: arXiv