Graphs of order n with locating-chromatic number n−1 Original Research Article

For a coloring c of a connected graph G, let Π=(C1,C2,…,Ck) 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,C1),d(v,C2),…,d(v,Ck)),where d(v,Ci)=min{d(v,x): x∈Ci} 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.