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 |
Externí odkaz: |
|