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 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.
@article{10_37236_2117,
author = {Karen L. Collins and Ann Trenk},
title = {Nordhaus-Gaddum theorem for the distinguishing chromatic number},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {3},
doi = {10.37236/2117},
zbl = {1298.05112},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2117/}
}
TY - JOUR
AU - Karen L. Collins
AU - Ann Trenk
TI - Nordhaus-Gaddum theorem for the distinguishing chromatic number
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/2117/
DO - 10.37236/2117
ID - 10_37236_2117
ER -
%0 Journal Article
%A Karen L. Collins
%A Ann Trenk
%T Nordhaus-Gaddum theorem for the distinguishing chromatic number
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/2117/
%R 10.37236/2117
%F 10_37236_2117
Karen L. Collins; Ann Trenk. Nordhaus-Gaddum theorem for the distinguishing chromatic number. The electronic journal of combinatorics, Tome 20 (2013) no. 3. doi: 10.37236/2117
