On irreducible no-hole L(2, 1)-coloring of Cartesian product of trees with paths
Nibedita Mandal, Pratima Panigrahi · AKCE International Journal of Graphs and Combinatorics · 2020
An L(2, 1)-coloring of a graph G is a mapping f:V(G)→Z+∪{0} such that |f(u)−f(v)|≥2 for all edges uv of G, and |f(u)−f(v)|≥1 if u and v are at distance two in G. The span of an L(2, 1)-coloring f of G, denoted by span(f), is max {f(v):v∈V(G)}. The span of G, denoted by λ(G), is the minimum span of all possible L(2, 1)-colorings of G. If f is an L(2, 1)-coloring of a graph G with span k then an integer l is a hole in f if l∈(0,k) and there is no vertex v in G such that f(v) = l. A no-hole coloring is defined to be an L(2, 1)-coloring with no hole in it. An L(2, 1)-coloring is said to be irreducible if the color of none of the vertices in the graph can be decreased and yield another L(2, 1)-coloring of the same graph. An irreducible no-hole coloring of a graph G, in short inh-coloring of G, is an L(2, 1)-coloring of G which is both irreducible and no-hole. A graph G is inh-colorable if there exists an inh-coloring of it. For an inh-colorable graph G the lower inh-span or simply inh-span of G, denoted by λinh(G), is defined as λinh(G)=min{span (f):f is an inh-coloring of G}. In this paper, we prove that the Cartesian product of trees with paths are inh-colorable.