On Trees with Locating-Chromatic Number and Dominating Partition Dimension Equal to Three

Abstract

Several graph parameters are defined through vertex partitions and distance representations.
Two such parameters are the locating-chromatic number $\chi_L(G)$ and the dominating partition dimension $\eta_p(G)$. The locating-chromatic number requires that vertices are distinguished by their distances to color classes, while the dominating partition dimension additionally imposes a domination condition, namely that every vertex must be adjacent to at least one partition class. It is known that for every connected graph $G$, $\beta_p(G)\le \eta_p(G)\le \chi_L(G)$, where $\beta_p(G)$ denotes the partition dimension. However, the conditions under which equality holds are not yet fully understood. In this paper, we focus on trees $T$ and show that the equality $\chi_L(T)=\eta_p(T)$ occurs exactly at value three. More precisely, we prove that a tree $T$ satisfies $\chi_L(T)=3$ if and only if $\eta_p(T)=3$. The proof is structural and is based on an analysis of leaf configurations and strong support vertices. In particular, we establish that the presence of two distinct strong support vertices forces $\eta_p(T)\ge 4$, preventing equality at value three. As a consequence, the class of trees with locating-chromatic number three coincides exactly with the class of trees whose dominating partition dimension equals three.