## Abstract

Let T be a finite or infinite tree and m the minimum number of vertices moved by the non-identity automorphisms of T. We give bounds on the maximum valence d of T that assure the existence of a vertex coloring of T with two colors that is preserved only by the identity automorphism. For finite m we obtain the bound d≤ 2
^{m}
^{/}
^{2} when T is finite, and d≤ 2
^{(}
^{m}
^{-}
^{2}
^{)}
^{/}
^{2}+ 2 when T is infinite. For countably infinite m the bound is d≤ 2
^{m}. This relates to a question of Babai, who asked whether there existed a function f(d) such that every connected, locally finite graph G with maximum valence d has a 2-coloring of its vertices that is only preserved by the identity automorphism if the minimum number m of vertices moved by each non-identity automorphisms of G is at least m≥ f(d). Our results give a positive answer for trees. The trees need not be locally finite, their maximal valence can be 2ℵ0. For finite m we also extend our results to asymmetrizing trees by more than two colors.

Original language | English |
---|---|

Pages (from-to) | 615-624 |

Number of pages | 10 |

Journal | Monatshefte für Mathematik |

Volume | 192 |

Issue number | 3 |

DOIs | |

Publication status | Published - 28 Jul 2020 |

Externally published | Yes |

## Keywords

- Asymmetric colorings
- Automorphisms
- Finite and infinite trees

## ASJC Scopus subject areas

- Mathematics(all)