L(2, 1)-coloring and irreducible no-hole coloring of lexicographic product of graphs

Abstract

An L(2, 1)-coloring (or labeling) of a graph G is a mapping [Formula: see text] such that [Formula: see text] if [Formula: see text] and [Formula: see text] if [Formula: see text] The span of an L(2, 1)-coloring is the maximum color assigned by it. The minimum of span of all possible L(2, 1)-colorings of a graph G is called the span of G and is denoted by [Formula: see text] An L(2, 1)-coloring f of a graph G is called (i) no-hole if f uses all the colors from [Formula: see text] (ii) irreducible if no color of the vertices can be decreased and yield another L(2, 1)-coloring of G, (iii) irreducible no-hole (in short inh-coloring) if f is both irreducible and no-hole. The inh-span of an inh-colorable graph G, denoted by [Formula: see text] is defined as [Formula: see text] The lexicographic product of two graphs G and H is the graph [Formula: see text] with vertex set [Formula: see text] in which two vertices (x, y) and [Formula: see text] are adjacent precisely if [Formula: see text] or [Formula: see text] and [Formula: see text] In this paper, we give improved upper bounds for span of lexicographic product of arbitrary graphs. We study inh-colorability of [Formula: see text] and [Formula: see text] where G is an arbitrary graph and T is a tree different from a star and a path. We show that for an arbitrary graph G1, if [Formula: see text] is inh-colorable then for any graph G2 with [Formula: see text] and [Formula: see text] is inh-colorable and [Formula: see text]

Keywords

• L(2, 1)-coloring
• no-hole coloring
• irreducible coloring
• span of a graph
• lexicographic product of graphs
• 05C15