On the locating chromatic number of Kneser graphs

Let cc be a proper kk-coloring of a connected graph GG and Π=(C1,C2,…,Ck)Π=(C1,C2,…,Ck) be an ordered partition of V(G)V(G) into the resulting color classes. For a vertex vv of GG, the color code of vv with respect to ΠΠ is defined to be the ordered kk-tuple cΠ(v):=(d(v,C1),d(v,C2),…,d(v,Ck))cΠ(v):=(d(v,C1),d(v,C2),…,d(v,Ck)), where d(v,Ci)=min{d(v,x)|x∈Ci},1≤i≤kd(v,Ci)=min{d(v,x)|x∈Ci},1≤i≤k. If distinct vertices have distinct color codes, then cc is called a locating coloring. The minimum number of colors needed in a locating coloring of GG is the locating chromatic number of GG, denoted by χL(G)χL(G). In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results, we show that χL(KG(n,2))=n−1χL(KG(n,2))=n−1 for all n≥5n≥5. Then, we prove that χL(KG(n,k))≤n−1χL(KG(n,k))≤n−1, when n≥k2n≥k2. Moreover, we present some bounds for the locating chromatic number of odd graphs.

► Studying the locating chromatic number of Kneser graphs KG(n,k)KG(n,k).
► It is proved that,χL(KG(n,2))=n−1χL(KG(n,2))=n−1 for all n≥5n≥5.
► It is proved that, χL(KG(n,k))≤n−1χL(KG(n,k))≤n−1, when n≥k2n≥k2.
► For all positive integers n≥7,n−4≤χL(KG(n,3))≤n−1n≥7,n−4≤χL(KG(n,3))≤n−1.
► For all positive integers k,k≥3,dimM(KG(2k+1,k))≤2k+1, and ⌈2kln2−118k−12ln(kπ)lnk⌉≤χL(KG(2k+1,k))≤2k+4.