# On the locating chromatic number of Kneser graphs

Research paper by **Ali Behtoei, Behnaz Omoomi**

Indexed on: **18 Jul '11**Published on: **18 Jul '11**Published in: **Mathematics - Combinatorics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

Let $c$ be a proper $k$-coloring of a connected graph $G$ and
$\Pi=(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 of $v$ with respect to
$\Pi$ is defined to be the ordered $k$-tuple
$$c_{{}_\Pi}(v):=(d(v,C_1),d(v,C_2),...,d(v,C_k)),$$ where
$d(v,C_i)=\min\{d(v,x) |x\in C_i\}, 1\leq i\leq k$. If distinct vertices have
distinct color codes, then $c$ is called a locating coloring. The minimum
number of colors needed in a locating coloring of $G$ is the locating chromatic
number of $G$, denoted by $\Cchi_{{}_L}(G)$. In this paper, we study the
locating chromatic number of Kneser graphs. First, among some other results we
show that $\Cchi_{{}_L}(KG(n,2))=n-1$ for all $n\geq 5$. Then, we prove that
$\Cchi_{{}_L}(KG(n,k))\leq n-1$, when $n\geq k^2$. Moreover, we present some
bounds for the locating chromatic number of odd graphs.