Geodetic coloring of graphs
RAIRO - Operations Research · 2026-07 · 60 (4) · 2253-2263
DOI: 10.1051/ro/2026075 ↗Kurz gefasst
Fachartikel in der Zeitschrift RAIRO - Operations Research, online erschienen am 28.07.2026. Verfasst von R. Srikantha und 1 weiteren Autor:innen. Die Arbeit nennt 11 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Srikantha, R., & Rangarajan, R. (2026). Geodetic coloring of graphs. RAIRO - Operations Research, 60(4), 2253-2263. https://doi.org/10.1051/ro/2026075
Vancouver
Srikantha R, Rangarajan R. Geodetic coloring of graphs. RAIRO - Operations Research. 2026;60(4):2253-2263. doi:10.1051/ro/2026075
BibTeX
@article{Srikantha2026,
author = {Srikantha, R. and Rangarajan, R.},
title = {Geodetic coloring of graphs},
journal = {RAIRO - Operations Research},
year = {2026},
volume = {60},
number = {4},
pages = {2253--2263},
doi = {10.1051/ro/2026075}
}
EUVIMED