Edge-locating coloring of graphs

Korivand, Meysam (Department of Mathematics, Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran)
Mojdeh, Doost Ali (Department of Mathematics, Faculty of Mathematical Sciences University of Mazandaran, Babolsar, Iran)
Baskoro, Edy Tri (Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesa 10 Bandung, Indonesia)
Erfanian, Ahmad (Department of Pure Mathematics, Faculty of Mathematical Sciences and Center of Excellence in Analysis on Algebraic Structures Ferdowsi University of Mashhad, P.O. Box 1159-91775, Mashhad, Iran)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 12, No 1 (2024): Electronic Journal of Graph Theory and Applications

An edge-locating coloring of a simple connected graph G is a partition of its edge set into matchings such that the vertices of G are distinguished by the distance to the matchings. The minimum number of the matchings of G that admits an edge-locating coloring is the edge-locating chromatic number of G, and denoted by χ′L(G). This paper introduces and studies the concept of edge-locating coloring. Graphs G with χ′L(G)∈{2, m} are characterized, where m is the size of G. We investigate the relationship between order, diameter and edge-locating chromatic number. We obtain the exact values of χ′L(Kn) and χ′L(Kn − M), where M is a maximum matching; indeed this result is also extended for any graph. We determine the edge-locating chromatic number of the join graphs of some well-known graphs. In particular, for any graph G, we show a relationship between χ′L(G + K1) and Δ(G). We investigate the edge-locating chromatic number of trees and present a characterization bound for any tree in terms of maximum degree, number of leaves, and the support vertices of trees. Finally, we prove that any edge-locating coloring of a graph is an edge distinguishing coloring.