Sum Coloring on Certain Classes of Graphs

Abstract

An $(2,1)$ \text{coloring} of a graph $G=(V,E)$ is a vertex coloring $f:V(G)\to \{0,1,2,\dots ,k\}$ such that $|f(u)–f(v)|\ge 2$ for all $uv\in E(G)$ and $|f(u)–f(v)|\ge 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)\to \{0,1,2,\dots ,\lambda (G)\}$ is onto and $f$ is an irreducible no-hole coloring (inh-coloring) if $f:V(G)\to \{0,1,2,\dots ,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)$.