Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number

Details Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number

2012-03-26

arxiv.org/abs/1203.5765v1

Mathematics

Combinatorics

18 pages

Scientific paper

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. Finck characterized the class of graphs that satisfy equality in this bound. In this paper, we provide a new characterization of this class of graphs, based on vertex degrees, which yields a new polynomial-time recognition algorithm and efficient computation of the chromatic number of graphs in this class. Our motivation comes from our theorem that generalizes the Nordhaus-Gaddum theorem to the distinguishing chromatic number: for any graph G, the distinguishing chromatic number of G plus the distinguishing chromatic number of G complement is less than or equal to the number of vertices of G plus the distinguishing number of G. Finally, we characterize those graphs that achieve equality in the sum upper bounds simultaneously for both the chromatic number and for our distinguishing chromatic number analog of the Nordhaus-Gaddum inequality.

Affiliated with

Also associated with

No associations

Rating

Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-642636