Abstract
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
χ
s
s
(
G
)
. In this paper we prove the NP-completeness of the problem, we discuss the
χ
s
s
(
G
)
number of trees by giving some bounds. Finally, we give an optimal polynomial algorithm for SSColoring of trees.