## Abstract

For a coloring c of a connected graph G, let Π = (C_{1}, C_{2},..., 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_{1}),d(v, C_{2}),..., 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.

Original language | English |
---|---|

Pages (from-to) | 65-79 |

Number of pages | 15 |

Journal | Discrete Mathematics |

Volume | 269 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 28 Jul 2003 |

Externally published | Yes |

## Keywords

- Locating set
- Locating-chromatic number
- Locating-coloring

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics