Graphs of order n with locating-chromatic number n - 1

For a coloring c of a connected graph G, let Π = (C₁, C₂,..., C_k) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code c_Π(v) of v is the ordered k-tuple (d(v, C₁),d(v, C₂),..., d(v,C_k)), where d(v,C_i) = min{d(v,x):x ∈ C_i} for 1 ≤ i ≤ k. If distinct vertices have distinct color codes, then c is called a locating-coloring. The locating-chromatic number χ_L(G) is the minimum number of colors in a locating-coloring of G. It is shown that if G is a connected graph of order n ≥ 3 containing an induced complete multipartite subgraph of order n - 1, then (n + 1)/2 ≤ χ_L(G) ≤ n and, furthermore, for each integer k with (n + 1)/2 ≤ k ≤ n, there exists such a graph G of order n with χ_L(G) = k. Graphs of order n containing an induced complete multipartite subgraph of order n-1 are used to characterize all connected graphs of order n ≥ 4 with locating-chromatic number n - 1.