Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number

  • Karen L. Collins
  • Ann Trenk
Keywords: Graph Theory, distinguishing number, distinguishing chromatic number, Nordhaus-Gaddum 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 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.

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

Published
2013-09-26
Article Number
P46