Faculty Publications
Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736
Publications by NITK Faculty
Browse
3 results
Search Results
Item Infinitely Many Trees with Maximum Number of Holes Zero, One, and Two(Hindawi Limited, 2018) Kola, S.R.; Gudla, B.; Niranjan, P.K.An L(2,1)-coloring of a simple connected graph G is an assignment f of nonnegative integers to the vertices of G such that fu-fv2 if d(u,v)=1 and fu-fv1 if d(u,v)=2 for all u,v∈V(G), where d(u,v) denotes the distance between u and v in G. The span of f is the maximum color assigned by f. The span of a graph G, denoted by (G), is the minimum of span over all L(2,1)-colorings on G. An L(2,1)-coloring of G with span (G) is called a span coloring of G. An L(2,1)-coloring f is said to be irreducible if there exists no L(2,1)-coloring g such that g(u)f(u) for all u∈V(G) and g(v)Item Some classes of trees with maximum number of holes two(Taylor and Francis Ltd., 2020) Kola, S.R.; Gudla, B.; Niranjan, P.K.An (Formula presented.) -coloring of a simple connected graph (Formula presented.) is an assignment of non-negative integers to the vertices of (Formula presented.) such that adjacent vertices color difference is at least two, and vertices that are at distance two from each other get different colors. The maximum color assigned in an (Formula presented.) -coloring is called span of that coloring. The span of a graph (Formula presented.) denoted by (Formula presented.) is the smallest span taken over all (Formula presented.) -colorings of (Formula presented.). A hole is an unused color within the range of colors used by the coloring. An (Formula presented.) -coloring (Formula presented.) is said to be irreducible if no other (Formula presented.) -coloring can be produced by decreasing a color of (Formula presented.). The maximum number of holes of a graph (Formula presented.), denoted by (Formula presented.), is the maximum number of holes taken over all irreducible (Formula presented.) -colorings with span (Formula presented.). Laskar and Eyabi (Christpher, 2009) conjectured that if (Formula presented.) is a tree, then (Formula presented.) if and only if (Formula presented.), (Formula presented.). We show that this conjecture does not hold by providing a counterexample. Also, we give some classes of trees with maximum number of holes two. © 2018 Kalasalingam University. Published with license by Taylor & Francis Group, LLC.Item L(2, 1)-coloring and its related problems for Mycielskians of certain classes of graphs(World Scientific, 2025) Kola, S.R.; Gudla, B.; Niranjan, P.K.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 ?inh(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 Cn(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.