Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.14402 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916799500517376 |
|---|---|
| author | Imrich, Wilfried Kalinowski, Rafał Lehner, Florian Pilśniak, Monika Stawiski, Marcin |
| author_facet | Imrich, Wilfried Kalinowski, Rafał Lehner, Florian Pilśniak, Monika Stawiski, Marcin |
| contents | Let $G$ be a finite or infinite graph and $m(G)$ the minimum number of vertices moved by the non-identity automorphisms of $G$. We are interested in bounds on the supremum $Δ(G)$ of the degrees of the vertices of $G$ that assure the existence of vertex colorings of $G$ with two colors that are preserved only by the identity automorphism, and, in particular, in the number $a(G)$ of such colorings that are mutually inequivalent.
For trees $T$ with finite $m(T)$ we obtain the bound $Δ(T)\leq2^{m(T)/2}$ for the existence of such a coloring, and show that $a(T)= 2^{|T|}$ if $T$ is infinite. Similarly, we prove that $a(G) = 2^{|G|}$ for all tree-like graphs $G$ with $Δ(G)\le 2^{\aleph_0}$.
For rayless or one-ended trees $T$ with arbitrarily large infinite $m(T)$, we prove directly that $a(T)= 2^{|T|}$ if $Δ(T)\le 2^{m(T)}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_14402 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Distinguishing finite and infinite trees of arbitrary cardinality Imrich, Wilfried Kalinowski, Rafał Lehner, Florian Pilśniak, Monika Stawiski, Marcin Combinatorics Let $G$ be a finite or infinite graph and $m(G)$ the minimum number of vertices moved by the non-identity automorphisms of $G$. We are interested in bounds on the supremum $Δ(G)$ of the degrees of the vertices of $G$ that assure the existence of vertex colorings of $G$ with two colors that are preserved only by the identity automorphism, and, in particular, in the number $a(G)$ of such colorings that are mutually inequivalent. For trees $T$ with finite $m(T)$ we obtain the bound $Δ(T)\leq2^{m(T)/2}$ for the existence of such a coloring, and show that $a(T)= 2^{|T|}$ if $T$ is infinite. Similarly, we prove that $a(G) = 2^{|G|}$ for all tree-like graphs $G$ with $Δ(G)\le 2^{\aleph_0}$. For rayless or one-ended trees $T$ with arbitrarily large infinite $m(T)$, we prove directly that $a(T)= 2^{|T|}$ if $Δ(T)\le 2^{m(T)}$. |
| title | Distinguishing finite and infinite trees of arbitrary cardinality |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2506.14402 |