Bounds for Distinguishing Invariants of Infinite Graphs
Preprint
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'(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.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Breaking graph symmetries by edge colouringsJournal of Combinatorial Theory, Series B, 2017
- Local Finiteness, Distinguishing Numbers, and Tucker's ConjectureThe Electronic Journal of Combinatorics, 2015
- Distinguishing graphs by total colouringsArs Mathematica Contemporanea, 2015
- Distinguishing graphs by edge-colouringsEuropean Journal of Combinatorics, 2015
- The Distinguishing Index of Infinite GraphsThe Electronic Journal of Combinatorics, 2015
- Distinguishing labellings of group action on vector spaces and graphsJournal of Algebra, 2006
- A Note on the Asymptotics and Computational Complexity of Graph DistinguishabilityThe Electronic Journal of Combinatorics, 1998
- Symmetry Breaking in GraphsThe Electronic Journal of Combinatorics, 1996
- Fixed elements of infinite treesDiscrete Mathematics, 1994
- Chromatic numbers of infinite graphsJournal of Combinatorial Theory, Series B, 1976