On the distinguishing chromatic number in hereditary graph classes
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912389371265024 |
|---|---|
| author | Brause, Christoph Kalinowski, Rafał Pilśniak, Monika Schiemeyer, Ingo |
| author_facet | Brause, Christoph Kalinowski, Rafał Pilśniak, Monika Schiemeyer, Ingo |
| contents | The distinguishing chromatic number of a graph $G$, denoted $χ_D(G)$, is the minimum number of colours in a proper vertex colouring of $G$ that is preserved by the identity automorphism only. Collins and Trenk proved that $χ_D(G)\le 2Δ(G)$ for any connected graph $G$, and the equality holds for complete balanced bipartite graphs $K_{p,p}$ and for $C_6$. In this paper, we show that the upper bound on $χ_D(G)$ can be substantially reduced if we forbid some small graphs as induced subgraphs of $G$, that is, we study the distinguishing chromatic number in some hereditary graph classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_17193 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the distinguishing chromatic number in hereditary graph classes Brause, Christoph Kalinowski, Rafał Pilśniak, Monika Schiemeyer, Ingo Combinatorics The distinguishing chromatic number of a graph $G$, denoted $χ_D(G)$, is the minimum number of colours in a proper vertex colouring of $G$ that is preserved by the identity automorphism only. Collins and Trenk proved that $χ_D(G)\le 2Δ(G)$ for any connected graph $G$, and the equality holds for complete balanced bipartite graphs $K_{p,p}$ and for $C_6$. In this paper, we show that the upper bound on $χ_D(G)$ can be substantially reduced if we forbid some small graphs as induced subgraphs of $G$, that is, we study the distinguishing chromatic number in some hereditary graph classes. |
| title | On the distinguishing chromatic number in hereditary graph classes |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2505.17193 |