Can you help me out in proving that the locating-chromatic number of $C_n$ for an even integer n is not 3?

Preliminary Concepts:

For a connected graph $G=(V,E$) of order $n$, the distance between two vertices $u$ and $v$ in $G$, denoted by $d(u,v)$, is the length of a shortest path from $u$ to $v$. Moreover, given subset $H$ of the vertex set $V(G)$, we define the distance, $d(v,H)$, from a vertex $v$ to a set $H$ as $d(v,H)$=$min$⁡{$d(v,h): h∈H$}.

A mapping $c:V(G)→K=${$1,2,…,k$} is said to be a proper $k$-coloring of the graph G if $c(a)≠c(b)$ for any two adjacent vertices $a$ and $b$. The set $K$ is referred to as the color set of $c$. The chromatic number of a graph $G$, denoted by $χ(G)$, is the smallest positive integer $k$ such that $G$ has a proper $k$-coloring. Thus, a partition $Π$ $=${$C_1,C_2,…,C_k $} of the vertex set $V(G)$ induced by the proper $k$-coloring $c$ of a graph contains the color classes $C_i$ where $C_i$ is the set of vertices receiving color $i$ for $i=1,2,…,k$.

Suppose $c$ is a proper vertex coloring of a graph $G$. The color code of a vertex $u$ of G with respect to $Π$, denoted by $c_Π (u)$, is the ordered $k$-tuple defined as $c_Π (u)=(d(u,C_1 ),d(u,C_2 ),…,d(u,C_k ) )$. If the vertices of $G$ have distinct color codes with respect to partition $Π$, i.e., $c_Π (v_i )≠c_Π (v_j )$ for each $u,v∈V(G)$, then coloring $c$ is called a locating-chromatic $k$-coloring or locating $k$-coloring of $G$. The smallest positive integer $k$ for which a graph $G$ has a locating $k$-coloring is referred to as the locating-chromatic number of graph $G$. This is denoted by $χ_L (G)$.

My concern:

I know that $χ_L (C_n) =4$ for an even integer $n$. I was able to show that the locating-chromatic number of $C_n$ is not 2 because the colors obviously alternate and hence, the color codes will share the same color code. Moreover, I am done in showing that $χ_L (C_n) =4$. All I need to show is $χ_L (C_n) \neq3$. Can you help me in showing that the locating-chromatic number is not equal to 3? Thank you so much!

  • $\begingroup$ When you say you're "done in showing $\chi_L(C_n)=4$ I think you mean $\chi_L(C_n)\le4$? How do you show that? $\endgroup$ – bof Oct 26 '16 at 4:59
  • $\begingroup$ Hi @bof! I am using the fact that $χ(G)≤χ_L (G)$. The theorem says that $χ_L(C_n)=4$ for an even $n$. Since $χ(G)=2$, then in the proof that I am doing, I am showing that there does not exists a locating $k$-coloring for $k$=2,3 and there is a locating $k$-coloring when $k=4$. What I meant by I am done in showing that $χ_L(C_n)=4$ is I already found a proper 4-coloring which is also a locating coloring. I also have an explanation why $χ_L(C_n)\neq2$. But, I can't find a way to prove that $χ_L(C_n)\neq3$. Thank you very much. $\endgroup$ – Jude Orgasan Oct 26 '16 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.