Geodetic coloring of graphs

A vertex subset S of a graph G = (V, E) is said to be geodetic set if every vertex in V − S lies in some geodesic of any two vertices in S. The minimum cardinality of a geodetic set of G is called as geodetic number of G, and is denoted by g(G). A geodetic coloring of a graph G is a proper vertex coloring of G in which every vertex in at least one geodetic set of G receives a different color. The minimum number of colors used in a geodetic coloring of G is called the geodetic chromatic number of G, and is denoted by χg(G). In this paper, we conduct a detailed study of χg(G), presenting existence results, bounds in relation to other graph parameters, and characterizations of graphs for which χg(G) = 2 and χg(G) = n, where n is the order of the graph. Furthermore, we prove that for every tree T, χg(T) equals the number of pendant vertices in T, unless T is a star or a path on odd vertices.