Sum Coloring on Certain Classes of Graphs

An \((2,1)\) \text{coloring} of a graph \( G = (V,E) \) is a vertex coloring \( f : V(G) \rightarrow \{0,1,2,\ldots,k\} \) such that \( |f(u) – f(v)| \geq 2 \) for all \( uv \in E(G) \) and \( |f(u) – f(v)| \geq 1 \) if \( d(u,v) = 2 \). The \emph{span} \( \lambda(G) \) is the smallest \( k \) for which \( G \) has an \( L(2,1) \) \text{coloring}. A \text{span coloring} is an \( L(2,1) \) coloring whose greatest color is \( \lambda(G) \). An \( L(2,1) \)-\text{coloring} \( f \) is a full-coloring if \( f : V(G) \rightarrow \{0,1,2,\ldots,\lambda(G)\} \) is onto and \( f \) is an irreducible no-hole coloring (inh-coloring) if \( f : V(G) \rightarrow \{0,1,2,\ldots,k\} \) is onto for some \( k \) and there does not exist an \( L(2,1) \)-\text{coloring} \( g \) such that \( g(u) < f(u) \) for all \( u \in V(G) \) and \( g(v) < f(v) \) for some \( v \in V(G) \). The Assignment sum of \( f \) on \( G \) is the sum of all the labels assigned to the vertices of \( G \) by the \( L(2,1) \) \text{coloring} \( f \). The \emph{Sum coloring number} of \( G \), introduced in this paper, \( \sum(G) \), is the minimum assignment sum over all the possible \( L(2,1) \) colorings of \( G \). \( f \) is a \text{Sum coloring} on \( G \) if its assignment sum equals the \emph{Sum coloring number}. In this paper, we investigate the \emph{Sum coloring numbers} of certain classes of graphs. It is shown that \( \sum(P_n) = 2(n – 1) \) and \( \sum(C_n) = 2n \) for all \( n \). We also give an exact value for the Sum coloring number of a star and conjecture a bound for the Sum coloring number of an arbitrary graph \( G \) with span \( \lambda(G) \).