Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number

Karen L. Collins, Ann Trenk

Nordhaus and Gaddum proved, for any graph G, that the chromatic number of G plus the chromatic number of G complement is less than or equal to the number of vertices in G plus 1. F…