Nordhaus-Gaddum theorem for the distinguishing chromatic number (Q396886)

Summary: \textit{E. A. Nordhaus} and \textit{J. W. Gaddum} [Am. Math. Mon. 63, 175--177 (1956; Zbl 0070.18503)] proved for any graph \(G\), that \(\chi(G) + \chi(\overline{G}) \leq n + 1\), where \(\chi\) is the chromatic number and \(n=|V(G)|\). \textit{H.-J. Finck} [in: Theory of Graphs, Proc. Colloq. Tihany, Hungary 1966, 99--113 (1968; Zbl 0157.55201)] characterized the class of graphs, which we call NG-graphs, that satisfy equality in this bound. In this paper, we provide a new characterization of NG-graphs, based on vertex degrees, which yields a new polynomial-time recognition algorithm and efficient computation of the chromatic number of NG-graphs. Our motivation comes from our theorem that generalizes the Nordhaus-Gaddum theorem to the distinguishing chromatic number. For any graph \(G, \chi_D(G) +\chi_D(\overline{G})\leq n+D(G)\). We call the set of graphs that satisfy equality in this bound NGD-graphs, and characterize the set of graphs that are simultaneously NG-graphs and NGD-graphs.