Graphs with large distinguishing chromatic number (Q1953399)

Summary: The distinguishing chromatic number \(\chi_D(G)\) of a graph \(G\) is the minimum number of colours required to properly colour the vertices of \(G\) so that the only automorphism of \(G\) that preserves colours is the identity. For a graph \(G\) of order \(n\), it is clear that \(1\leq\chi_D(G)\leq n\), and it has been shown that \(\chi_D(G)=n\) if and only if \(G\) is a complete multipartite graph. This paper characterizes the graphs \(G\) of order \(n\) satisfying \(\chi_D(G)=n-1\) or \(\chi_D(G)=n-2\).