Some New Results on ?(k) -Coloring of Graphs
bad edges; Improper coloring; near proper coloring; ?(k) -coloring
Let ? be the minimum number of distinct resources or equipment such as channels, transmitters, antennas and surveillance equipment required for a system's stability. These resources are placed on a system. The system is stable only if the resources of the same type are placed far away from each other or, in other words, they are not adjacent to each other. Let these distinct resources represent different colors assigned on the vertices of a graph G. Suppose the available resources, denoted by k, are less than ?. In that case, placing k resources on the vertices of G will make at least one equipment of the same type adjacent to each other, which thereby make the system unstable. In ?(k)-coloring, the adjacency between the resources of a single resource type is tolerated. The remaining resources are placed on the vertices so that no two resources of the same type are adjacent to each other. In this paper, we discuss some general results on the ?(k)-coloring and the number of bad edges obtained from the same for a graph G. Also, we determine the minimum number of bad edges obtained from ?(k)-coloring of few derived graph of graphs. The number of bad edges which result from a ?(k)-coloring of G is denoted by bk(G). 2023 World Scientific Publishing Company.
Ellumkalayil M.T.; Samuel L.C.; Naduvath S.
Journal of Interconnection Networks, Vol-23, No. 3
Ellumkalayil M.T., School of Sciences, Christ University, Delhi NCR, 201003, India; Samuel L.C., Department of Computer Science, Dasve Lavasa, Mulshi, Pune, India; Naduvath S., Department of Mathematics, Christ University, Bangalore, India