On the locating chromatic number of Kneser graphs

Abstract: Let

c

be a proper

k

-coloring of a connected graph

G

and

P i = (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

P i

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}) = m i n d (v, x) | x i n C_{i}, 1 l e q i l e q 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

C c h i_{_{L}} (G)

. In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results we show that

C c h i_{_{L}} (K G (n, 2)) = n - 1

for all

n g e q 5

. Then, we prove that

C c h i_{_{L}} (K G (n, k)) l e q n - 1

, when

n g e q k^{2}

. Moreover, we present some bounds for the locating chromatic number of odd graphs.

Cites Work

Cited In (11)

This page was built for publication: On the locating chromatic number of Kneser graphs