Sum Coloring on Certain Classes of Graphs

Gilbert Eyabi1, Renu Laskar1
1Department of Mathematical Sciences, Clemson University

Abstract

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 \({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 \({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 \({Sum\; coloring\; number}\). In this paper, we investigate the \({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) \).

Keywords: \( L(2,1) \) colorings; inh-coloring; Sum coloring, Sum Coloring Number; Channel assignment problems.