A strict strong coloring of trees

In this paper we introduce and study a new coloring parameter of a graph called the strict strong coloring (short SSColoring). A SSColoring of a graph G is a vertex proper coloring of G such that each vertex of G is adjacent to at least one not empty color class. The minimum number of colors among all SSColorings is called strict strong chromatic (short SSChromatic) number, denoted by χss(G). In this paper we prove the NP-completeness of the problem, we discuss the χss(G) number of trees by giving some bounds. Finally, we give an optimal polynomial algorithm for SSColoring of trees.