Graphs of order \(n\) with locating-chromatic number \(n-1\) (Q1402068)

For a coloring \(c\) of a connected graph \(G\), let \(\Pi=(C_{1},\dots,C_{k})\) be an ordered partition of \(V(G)\) into the resulting color classes. For a vertex \(v\in V(G)\), the \(k\)-tuple \((d(v,C_{1}),\dots ,d(v,C_{k}))\), where \(d(v,C_{i})=\min\{d(v,x):x\in C_{i}\}\) for \(1\leq i\leq k\) is called the color code \(c_{\Pi}(v)\) of \(v\). If distinct vertices have distinct color codes, then \(c\) is called a locating-coloring. The locating-chromatic number \(\chi _{L}(G)\) is defined as the minimum number of colors in a locating-coloring of \(G\). In this paper it is shown that if \(G\) is a connected graph of order \(n\geq 3\) containing an induced multipartite subgraph of order \(n-1\), then \((n+1)/2\leq \chi _{L}(G)\leq n\) and, furthermore, for each integer \(k\) with \((n+1)/2\leq k\leq n\), there exists such a graph \(G\) of order \(n\) with \(\chi _{L}(G)=k\). Connected graphs of order \(n\geq 4\) having locating-chromatic number \(n-1\) are characterized by means of two families of graphs of order \(n\) containing an induced complete multipartite subgraph of order \(n-1\).