Geodetic coloring of graphs

¹ Department of Mathematics, Government College for Women, Chintamani 563125, Karnataka, India
² Department of Studies in Mathematics, University of Mysore, Mysuru 570006, Karnataka, India

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 24 June 2025
Accepted: 9 June 2026

Abstract

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.