Coupon coloring of cographs

Coupon coloring is a new coloring which has many applications. A k -coupon coloring of a graph G is a k -coloring of G by colors [ k ] = { 1 , 2 , … , k } such that the neighborhood of every vertex of G contains vertices of all colors from [ k ]. The maximum integer k for which a k -coupon coloring exists is called the coupon coloring number of G , and it is denoted by χ c ( G ). In this paper, we studied the coupon coloring of cographs, which are graphs that can be generated from the single vertex graph K 1 by complementation and disjoint union, and have applications in many interesting problems. We use the cotree representation of a cograph to give a polynomial time algorithm to color the vertices of a cograph, and then prove that this coloring is a coupon coloring with maximum colors, hence get the coupon coloring numbers of the cograph.