Minimal coloring and strength of graphs (Q1974540)

A proper vertex coloring \(c\) of a graph \(G\) using colors \(1,2,\dots\) is said to be minimal if \(\sum_{v\in V(G)} c(v)\) is minimum among all vertex colorings of \(G\). The vertex strength of \(G\), denoted by \(s(G)\), is the smallest number of colors needed to obtain a minimal coloring of \(G\). (The edge strength of \(G\), denoted by \(s'(G)\), is similarly defined.) The coloring number of \(G\), denoted by \(\text{col}(G)\), is the smallest number \(d\) such that for some linear ordering \(<\) of the vertex set of \(G\), the back degree \(|\{v: v<u\) and \(vu\in E(G)\}|\) of each vertex \(u\) of \(G\) is strictly less than \(d\). These notions have been studied by E. Kubicka and others in 1989-1990. In this paper, the following results are proved: (1) For any connected graph \(G\), \(s(G)= \Delta(G)+1\) if and only if \(G\) is a complete graph or an odd cycle. (2) \(s(G)\leq [{\text{col}(G)+ \Delta(G)\over 2}]\). (3) \(\Delta(G)\leq s'(G)\leq \Delta(G)+ 1\).