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 $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 $Sumcoloringnumber$ 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 $Sumcoloringnumber$. In this paper, we investigate the $Sumcoloringnumbers$ 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)$.