A note on relaxed equitable coloring of graphs

In this note we introduce the concept of equitable d-relaxed coloring. We prove that each graph with maximum degree at most r admits an equitable 1-relaxed r-coloring and provide a polynomial-time algorithm for constructing such a coloring.

► The concept of equitable d-relaxed coloring is introduced.
► An upper bound for the equitable d-relaxed threshold is given.
► A fast algorithm for constructing an equitable 1-relaxed coloring is provided.