Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number

作者：Collins Karen L^*; Trenk Ann

来源：Electronic Journal of Combinatorics, 2013, 20(3): P46.

• distinguishing number
• distinguishing chromatic number
• chromatic number
• Nordhaus-Gaddum theorem

Nordhaus and Gaddum proved, for any graph G, that x(G) + x((G) over bar) %26lt;= n + 1, where chi is the chromatic number and n = vertical bar V(G)vertical bar. 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)((G) over bar) %26lt;= 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.

• 出版日期2013-9-26