L(2, 1)-coloring and its related problems for Mycielskians of certain classes of graphs

Abstract

In an L(2, 1)-coloring f of G with span k, h ?{0, 1, 2,…,k} is a hole if there is no vertex v in G such that f(v) = h. An L(2, 1)-coloring with span k is said to be a no-hole coloring if it uses all the colors from {0, 1, 2,…,k}. An L(2, 1)-coloring of a graph G is irreducible if color of no vertex can be decreased and yield another L(2, 1)-coloring of G. A graph G is inh-colorable if there exists an irreducible no-hole coloring of G. The inh-span of a graph G, denoted by ?<inf>inh</inf>(G) is the smallest number k such that there is an irreducible no-hole L(2, 1)-coloring of G with span k. The maximum number of holes in G is the maximum number of holes over all irreducible span colorings of G. In this paper, we give an algorithm to define an L(2, 1)-coloring for the Mycielskian ?(G) of an arbitrary graph G. We prove that the algorithm gives span colorings for Mycielskians of path Pn (n ? 16), cycle C<inf>n</inf>(n ? 19), some classes of trees and concatenation of an arbitrary graph with trees. Also, we show that the Mycielskians for the above classes of graphs are inh-colorable and their inh-span is same as the ?-number. Further, we determine the maximum number of holes over all irreducible span colorings for Mycielskians of path Pn (n ? 17), cycle Cn (n ? 20), some classes of trees and concatenation of an arbitrary graph with trees. © 2025 World Scientific Publishing Company.