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$.
@article{10_37236_2407,
author = {Michael Cavers and Karen Seyffarth},
title = {Graphs with large distinguishing chromatic number},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {1},
doi = {10.37236/2407},
zbl = {1266.05025},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2407/}
}
TY - JOUR
AU - Michael Cavers
AU - Karen Seyffarth
TI - Graphs with large distinguishing chromatic number
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/2407/
DO - 10.37236/2407
ID - 10_37236_2407
ER -
%0 Journal Article
%A Michael Cavers
%A Karen Seyffarth
%T Graphs with large distinguishing chromatic number
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/2407/
%R 10.37236/2407
%F 10_37236_2407
Michael Cavers; Karen Seyffarth. Graphs with large distinguishing chromatic number. The electronic journal of combinatorics, Tome 20 (2013) no. 1. doi: 10.37236/2407
