On the locating chromatic number of Kneser graphs

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\le i\le 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\ge 5$. Then, we prove that $\Cchi_{{}_L}(KG(n,k))\leq n-1$, when $n\ge k^2$. Moreover, we present some bounds for the locating chromatic number of odd graphs.

To appear in D.A.M