Minimal coloring and strength of graphs

AbstractLet G be a graph. A minimal coloring of G is a coloring which has the smallest possible sum among all proper colorings of G, using natural numbers. The vertex-strength of G, denoted by s(G), is the minimum number of colors which is necessary to obtain a minimal coloring. In this note we study these concepts, and define a new concept called the edge-strength of G, denoted by s′(G). We prove the celebrated Brooks’ theorem for χ(G) replaced by s(G) and we also prove the following upper bound for s(G):s(G)⩽col(G)+Δ(G)2,where col(G) is an invariant based on linear orderings of the vertices. Also, it is proved that s′(G) lies between Δ(G) and Δ(G)+1, as for χ′(G), but it may be not equal to χ′(G). Based on our results about vertex-strength we conjectures(G)⩽χ(G)+Δ(G)2