EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Geodetic coloring of graphs

R. Srikantha, R. Rangarajan

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →