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

Gary Chartrand, David Erwin, Michael A. Henning, Peter J. Slater, Ping Zhang

Research output: Contribution to journalArticlepeer-review

46 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)65-79
Number of pages15
JournalDiscrete Mathematics
Volume269
Issue number1-3
DOIs
Publication statusPublished - 28 Jul 2003
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Graphs of order n with locating-chromatic number n - 1'. Together they form a unique fingerprint.

Cite this