On the distinguishing chromatic number in hereditary graph classes

Christoph Brause; Rafał Kalinowski; Monika Pilśniak; Ingo Schiemeyer

paper

On the distinguishing chromatic number in hereditary graph classes

arXiv:2505.17193

Abstract

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) \leq 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.