
Karen L. Collins

Ann Trenk
Keywords:
Graph Theory, distinguishing number, distinguishing chromatic number, NordhausGaddum theorem
Abstract
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 NGgraphs, that satisfy equality in this bound. In this paper, we provide a new characterization of NGgraphs, based on vertex degrees, which yields a new polynomialtime recognition algorithm and efficient computation of the chromatic number of NGgraphs. Our motivation comes from our theorem that generalizes the NordhausGaddum 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 NGDgraphs, and characterize the set of graphs that are simultaneously NGgraphs and NGDgraphs.
Author Biographies
Karen L. Collins, Wesleyan University
Professor of Mathematics
Department of Mathematics and Computer Science
Ann Trenk, Wellesley College
Professor of Mathematics
Department of Mathematics