






















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。