Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number

[摘要] Nordhaus and Gaddum proved, for any graph $G$, that $\chi(G) + \chi(\overline{G}) \leq n + 1$, where $\chi$ is the chromatic number and $n=|V(G)|$. Finck characterized the class of graphs, which we call NG-graphs, that satisfy equality in this bound. In t

[学科分类] 离散数学和组合数学

[关键词] Graph Theory;distinguishing number;distinguishing chromatic number;Nordhaus-Gaddum theorem