Characterizing all trees with locating-chromatic number 3

Edy Tri Baskoro, Asmiati

Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesa 10 Bandung, Indonesia

ebaskoro@math.itb.ac.id, asmiati308@students.itb.ac.id

Let c be a proper k-coloring of a connected graph G. Let Π = {S1, S2, . . . , Sk} be the induced partition of V (G) by c, where Sⁱ is the partition class having all vertices with color i. The color code cΠ(v) of vertex v is the ordered k-tuple (d(v, S1), d(v, S2), . . . , d(v, Sk)), where d(v, Si) = min{d(v, x)|x ∈ Si}, for 1 ≤ i ≤ k. If all vertices of G have distinct color codes, then c is called a locating-coloring of G. The locating-chromatic number of G, denoted by χL(G), is the smallest k such that G posses a locating k-coloring. Clearly, any graph of order n ≥ 2 has locating-chromatic number k, where 2 ≤ k ≤ n. Characterizing all graphs with a certain locating-chromatic number is a difficult problem. Up to now, all graphs of order n with locating chromatic number 2, n − 1, or n have been characterized. In this paper, we characterize all trees whose locating-chromatic number is 3. We also give a family of trees with locating-chromatic number 4.

Keywords: Locating-chromatic number, graph, tree. Mathematics Subject Classification : 05C12.

1. Introduction

Chartrand et al. [8] initiated the study on the locating-chromatic number of a graph. This notion is a special case of the partition dimension of a graph, namely the smallest integer k in which there exists a k-partition Π of the graph such that the coordinates of all vertices with respect to Π are distinct. Since then, various results have been obtained by different authors. However,

Received: 23 May 2013, Revised: 7 October 2013, Accepted: 23 October 2013.

determining the locating-chromatic number of any graph in general is classified as an NP-hard problem [8]. Furthermore, characterizing all graphs with a certain locating-chromatic number is also a difficult question.

In this paper, we consider only simple connected graphs. Let G(V, E) be a graph. The distance d(u, v) from vertex u to vertex v in G is the length of a shortest path from u to v. For S ⊆ V (G), define the distance d(v, S) from vertex v to set S as min{d(v, x)|x ∈ S}. Let c be a k-coloring of G and Π = {S1, S2, · · · , Sk} be a partition of V (G) induced by c, where Sⁱ is the set of vertices receiving color i. The color code cΠ(v) of v is defined as the ordered k-tuple (d(v, S1), d(v, S2), . . . , d(v, Sk)). If all vertices of G have distinct color codes, then c is called a locating-chromatic k-coloring of G (k-locating coloring, in short). The locating-chromatic number χL(G) of graph G is the smallest k such that G has a locating k-coloring.

Chartrand et al. [8] determined the locating-chromatic numbers for some well-known classes of graphs, namely paths, cycles, complete multipartite graphs and double stars. The locatingchromatic number of a path Pⁿ is 3, for n ≥ 3. The locating-chromatic number of a cycle Cⁿ is 3 if n is odd and 4 otherwise. Furthermore, Chartrand et al. [9] studied the locating-chromatic number of trees in general. They showed that for any integer k ∈ {3, 4, ..., n − 2, n}, there exists a tree of order n with locating-chromatic number k. They also showed that no tree of order n exists with locating-chromatic number n − 1. Recently, Asmiati et al. [1, 3], determined the locating-chromatic number for an amalgamation of stars and firecracker graphs.

Some authors also consider the locating-chromatic number for graphs produced by a graph operation. For instances, Baskoro and Purwasih [4] determined the locating-chromatic number for the corona product of two graphs. Behtoei and Omoomi obtained the locating-chromatic number for the Cartesian product of graphs [6] and for the join product of graphs [7]. In particular, they also obtained the locating chromatic number of the fans, wheels and friendship graphs. In [5], Behtoei and Omoomi also considered the locating chromatic number of Kneser graphs.

Certainly, the only graph with locating-chromatic number n is a multipartite complete graph with n vertices. Furthermore, Chartrand et al. [9] also characterized all graphs on n vertices whose locating-chromatic number is n−1. In the same paper, they showed that if G is a connected graph of order n ≥ 5 containing an induced subgraph F ∈ {2K¹ ∪ K2, P² ∪ P3, H1, H2, H3, P² ∪ K3, P2, C5, C⁵ + e}, then χL(G) ≤ n − 2. All graphs of order n with locating-chromatic number 3 are still not fully characterized. We know that Pn, n ≥ 3, is an example of a graph with locatingchromatic number 3. Recently, we characterized all graphs containing a cycle with the locatingchromatic number 3 [2]. In this paper, we will determine all trees with locating-chromatic number 3. Therefore, this paper will complete the characterization of all graphs with locating-chromatic number 3. We also give a family of trees with locating-chromatic number 4.

2. Basic Properties

In this section, we give some definitions and basic properties related to graphs with locatingchromatic number 3. Let c be a locating k-coloring on graph G(V, E). Let Π = {S1, S2, · · · , Sk} be the partition of V (G) induced by c. A vertex v ∈ G is called a dominant vertex if d(v, Si) = 1 if v 6∈ Sⁱ . A path connecting two dominant vertices in G is called a clear path if all of its internal

vertices are not dominant. Then, we have the following lemma as a direct consequence of the definition of dominant vertices.

Lemma 2.1. [2] Let G be a graph with χL(G) = k. Then, there are at most k dominant vertices in G and all of them must receive different colors.

Lemma 2.2. [3] Let G be a graph with χL(G) = 3. Then, the length of any clear path in G is odd.

Lemma 2.3. [3] Let G be a connected graph with χL(G) = 3. If G contains three dominant vertices, then these three dominant vertices must lie in a path.

3. Characterization

Consider two specific caterpillars C(2, 2, 2) and C(2, 1, t z }| { 0, · · · , 0, 1, 2), for any odd t, as depicted in the left side of Figure 1. Let G¹ be the subdivision of C(2, 2, 2) on six pendant edges in t

k1, k2, · · · , k⁶ times respectively, where kⁱ ≥ 1. Let G² be the subdivision of C(2, 1, z }| { 0, · · · , 0, 1, 2) on six pendant edges in k1, k2, · · · , k⁶ times respectively, where kⁱ ≥ 1.

Figure 1. The specific caterpillars and their subdivisions.

Let T be the class of all trees whose locating-chromatic number is 3. In this section, we characterize all trees which are members of T .

Lemma 3.1. Let T ∈ T . The color code of any vertex of T is (c1, c2, c3) such that {c1, c2, c3} = {0, 1, k} where k ≥ 1.

Proof. Let x ∈ T and without loss of generality assume c(x) = 1. Since the neighbor of x must have a different color then the color code of x is either (0, 1, k) or (0, k, 1), where k ≥ 1.

For any integer k ≥ 1, a tree T ∈ T is called k-maximal if T has all possible color codes with k is the maximum ordinate. In this case, there is a locating coloring of T such that each color class in T has exactly 2k − 1 vertices. For example, graph C(2, 2, 2) is 2-maximal, since this graph has a locating coloring with each color class having 3 vertices. It can be verified that a path on 6k − 3 vertices is k-maximal. However, not all tree on 6k − 3 vertices are k-maximal.

Lemma 3.2. Let T ∈ T . Every vertex x of T has degree at most 4.

Proof. To the contrary, assume there is a vertex x with d(x) ≥ 5. Let a1, a2, a3, a4, a⁵ be the neighbors of x. Let c be a locating 3-coloring of T. Assume c(x) = 1 and so c(ai) is either 2 or 3, for any i ∈ {1, 2, 3, 4, 5}. If there are i 6= j such that c(ai) 6= c(a^j ) then there are at least three vertices aⁱ with the same color, say color 2. Thus, two of these vertices will have the same color code, a contradiction. Now, assume that the colors of all vertices aⁱ are the same, say c(ai) = 2, for all i ∈ {1, 2, · · · , 5}. Let r = min{d(aⁱ , S3)| i = 1, 2, · · · , 5}, where S³ is the partition class consisting of all vertices whose color is 3. Then, the possible color codes for vertices aⁱ are (1, 0, r),(1, 0, r + 1), or (1, 0, r + 2). Therefore, we will have two vertices aⁱ with the same color code, a contradiction.

From now on, let T ∈ T . By Lemma 2.1, T has at most three dominant vertices. Clearly, if T is either a path P3, or P4, a double star S1,² or S2,2, then T has a locating coloring such that T has only one or two dominant vertices. If T is not isomorphic to one of them, then T must have exactly three dominant vertices. Let x, y, z be their dominant vertices. Up to isomorphism, assume that c(x) = 1, c(y) = 2 and c(z) = 3. By Lemma 2.3, there are two clear paths in T: one connecting vertices x to y, and the other one connecting y to z. Let the two paths be ^xP^y := (x = u0, u1, u2, · · · , ur−1, u^r = y) and ^yP^z := (y = v0, v1, v2, · · · , vs−1, v^s = z) with r, s odd. Then, c(ui) = 1 for even i and 2 for odd i; and c(vi) = 2 for even i and 3 for odd i. Otherwise, there would be the fourth dominant vertex in T. Since x is a dominant vertex in T, then d(x) ≥ 2. Therefore, there must be a neighbor of x (other than u1), say a with c(a) = 3. Similarly, there must be a vertex b, a neighbor of z (other than vs−1), with c(b) = 1. So, we have a path P, where P = (a, x, u1, u2, · · · , ur−1, u^r = y, v1, v2, · · · , vs−1, v^s = z, b), with r, s odd. If r, s > 1 then define u ^∗ = u^b r ^c, u ∗∗ = u^b r+1 2 , v ^∗ = v^b s ^c, and v ∗∗ = v^b s+1 2 .

Lemma 3.3. If r = s = 1 then 1 ≤ d(a) ≤ 2, 2 ≤ d(x) ≤ 3, 2 ≤ d(y) ≤ 4, 2 ≤ d(z) ≤ 3, and 1 ≤ d(b) ≤ 2. Furthermore, every vertex w ∈ V (T)\P has degree at most 2 and is connected by a unique shortest path to one of {a, x, y, z, b}.

Proof. For a contradiction, assume d(a) ≥ 3 then two neighbors of a other than x will receive color 1. However, this implies that these neighbors will have the same color code, a contradiction. Therefore, d(a) ≤ 2. Similarly, we also conclude that d(b) ≤ 2. Next, since x is a dominant vertex, then d(x) ≥ 2. Now, assume that d(x) ≥ 4. Then, two of the neighbors of x will have the same color codes, a contradiction. Therefore, 2 ≤ d(x) ≤ 3. Similarly, we have that 2 ≤ d(z) ≤ 3. Since y is a dominant vertex and by Lemma 3.2 we have that 2 ≤ d(y) ≤ 4.

Let w ∈ V (T)\P. Since T is a tree, then there exists a unique shortest path L connecting w to a vertex of P. If d(w) ≥ 3 then there are two neighbors of w, say w¹ and w2, which are not in L. Since χL(T) = 3 and x, y and z are the dominant vertices of T then the color codes of w¹

and w² will be the same, a contradiction. Therefore, every vertex V (T)\P must have degree at most 2. The path L which connects w to P is unique (since T is a tree) and goes through one of {a, x, y, z, b}.

Lemma 3.4. If r = 1 and s > 1 then 1 ≤ d(a) ≤ 2, 2 ≤ d(x) ≤ 3, 2 ≤ d(y) ≤ 3, 2 ≤ d(v ∗ ) ≤ 3, 2 ≤ d(v ∗∗) ≤ 3, d(z) = 2, and 1 ≤ d(b) ≤ 2. All the other internal vertices vⁱ in P have degree 2. Furthermore, every vertex w ∈ V (T)\P has degree at most 2 and is connected by a unique shortest path to one of {a, x, y, b, v^∗ , v∗∗}.

Proof. To show 1 ≤ d(a) ≤ 2, 2 ≤ d(x) ≤ 3, 2 ≤ d(y) ≤ 3, and d(b) ≤ 2, we use a similar argument as in Lemma 3.3. Next, since v ∗ and v ∗∗ are internal vertices in P, then d(v ∗ ), d(v ∗∗) ≥ 2. Assume d(v ∗ ) ≥ 4. Since v ∗ is not a dominant vertex then its two neighbors not in P will receive the same color. This implies that their color codes are the same, a contradiction. Therefore, d(v ∗ ) ≤ 3. Similarly, we have d(v ∗∗) ≤ 3. If z has the third neighbor z¹ then the color code of z¹ will be the same as the color code of either vs−¹ or b. Therefore, d(z) = 2. Now, let vⁱ be any internal vertex in ^yP^z other than v ^∗ or v ∗∗. Assume d(vi) ≥ 3. Since all the neighbors of vⁱ are not dominant vertices, they will receive the same color. Thus, two of them will have the same color code, a contradiction. Therefore, d(vi) = 2 for any vⁱ other than v ∗ and v ∗∗ .

Let w ∈ V (T)\P. Since T is a tree, then there exists a unique shortest path L connecting w to a vertex of P. If d(w) ≥ 3 then there are two neighbors of w, say w1, w2, which are not in L. Since χL(T) = 3 and x, y and z are the dominant vertices of T then the color codes of w¹ and w² will be the same, a contradiction. Therefore, every vertex V (T)\P has degree at most 2. The path L which connects w to P is unique (since T is a tree) and goes through one of {a, x, y, b, v^∗ , v∗∗}.

Lemma 3.5. If r > 1 and s > 1 then 1 ≤ d(a) ≤ 2, d(x) = d(y) = d(z) = 2, 2 ≤ d(u ∗ ) ≤ 3, 2 ≤ d(u ∗∗) ≤ 3, 2 ≤ d(v ∗ ) ≤ 3, 2 ≤ d(v ∗∗) ≤ 3, and d(b) ≤ 2. All the other internal vertices in P have degree 2. Furthermore, every vertex w ∈ V (T)\P has degree at most 2 and is connected by a unique shortest path to one of {a, b, u^∗ , u∗∗, v^∗ , v∗∗}.

Proof. The proof is similar as in the proof of Lemma 3.4.

Theorem 3.1. If T ∈ T and T has maximum number of vertices of degree higher than 2, then T is isomorphic to either G¹ or G2.

Proof. Let T ∈ T . By Lemma 2.1, T contains at most three dominant vertices. If T is either a path P3, or P4, a double star S1,² or S2,2, then T has a locating coloring such that T has only one or two dominant vertices. If T is not isomorphic to one of these four graphs above, then T will have a locating coloring with exactly three dominant vertices. Let x, y, z be such vertices. Then by Lemma 2.3, there are two clear paths, namely: ^xP^y = (x = u0, u1, u2, · · · , ur−1, u^r = y), ^yP^z = (y = v0, v1, v2, · · · , vs−1, v^s = z), with r, s odd.

If r = s = 1 then by Lemma 3.3, T will have maximum number of vertices of degree higher than 2 if there are two paths attached to y and one path attached to each vertex of a, x, z, and b, as depicted in Figure 2(i). Now, define a coloring c : V (T) → {1, 2, 3} such that:

1. \[c(a) = 3, c(x) = 1, c(y) = 2, c(z) = 3, c(b) = 1;\]

• 2. The colors of vertices of the path L^a attached to a are 1 and 3 alternately;
• 3. The colors of vertices of the path L^x attached to x are 2 and 1 alternately;
• 4. The colors of vertices of the first path L 1 y attached to y are 1 and 2 alternately;
• 5. The colors of vertices of the second path L 2 y attached to y are 3 and 2 alternately;
• 6. The colors of vertices of the path L^z attached to z are 2 and 3 alternately;
• 7. The colors of vertices of the path L^b attached to b are 3 and 1 alternately.

The color codes of all vertices of L^a are (1, even, 0) or (0, odd, 1). The color codes of all vertices of L^x are (0, 1, odd) or (1, 0, even). The color codes of all vertices of L 1 y are (0, 1, even) or (1, 0, odd). The color codes of all vertices of L 2 y are (odd, 0, 1) or (even, 1, 0). The color codes of all vertices of L^z are (even, 0, 1) or (odd, 1, 0). The color codes of all vertices of L^b are (0, even, 1) or (1, odd, 0). Therefore, all the color codes are different. Thus, c is a locating-coloring on T. Since 3 is the smallest possible number of colors then χL(T) = 3. In this case, T is isomorphic to G1.

If r = 1 and s > 1 then by Lemma 3.4, T will have maximum number of vertices of degree higher than 2 if there is one path attached to vertices a, x, y, v^∗ , v∗∗ and b each as depicted in Figure 2(ii). Now, define a coloring c : V (T) → {1, 2, 3} such that:

• 1. c(a) = 3, c(x) = 1, c(y) = 2, c(z) = 3, c(b) = 1;
• 2. The colors of vertices of the path L^a attached to a are 1 and 3 alternately;
• 3. The colors of vertices of the path L^x attached to x are 2 and 1 alternately;
• 4. The colors of vertices of the path L^y attached to y are 1 and 2 alternately;
• 5. The colors of internal vertices vis are 3 and 2 alternately;
• 6. The colors of vertices of the path L^{v ∗} attached to v ∗ are 2 and 3 alternately;
• 7. The colors of vertices of the path L^v ∗∗ attached to v ∗∗ are 3 and 2 alternately;
• 8. The colors of vertices of the path L^b attached to b are 3 and 1 alternately.

Then, it can be verified that the color codes of all vertices in T are distinct. Therefore, c is a locating-coloring on T. Since 3 is the smallest possible number of colors then χL(T) = 3. In this case, T is isomorphic to G2.

If r > 1 and s > 1 then by Lemma 3.5, T will have maximum number of vertices of degree higher than 2 if there is one path attached to a, u^∗ , u∗∗, v^∗ , v∗∗ and b each, as depicted in Figure 1(iii). By defining a similar coloring c we can obtain χL(T) = 3. In this case, T is isomorphic to G2.

Theorem 3.2. A tree T has the locating-chromatic number 3 if and only if T is either a path P³ or P4, a double star S1,² or S2,² or a subtree containing a path P of either G¹ or G2.

Proof. If T is either P3, P4, S1,² or S2,² then clearly it has locating-chromatic number 3. Now, let T ^∗ be a subtree of either G¹ or G2, and it contains a path P of length at least 4, as illustrated in Figure 2. Then, by using the coloring c in Theorem 3.1 restricted to the subtree T ∗ , we obtain that all the color codes are different. Therefore, χL(T ∗ ) = 3.

Conversely, let T be a tree with locating-chromatic number 3. If the diameter of T is ≤ 3 then T must be either P3, P4, S1,² or S2,2. Now, if the diameter of T is ≥ 4 then by Lemma 2.1 T has at

Figure 2. A tree T ∈ T with maximum number of vertices of degree higher than 2 and it contains a path P = {a, x, u1, · · · , u^r = y, v1, · · · , v^s = z, b}.

most 3 dominant vertices. Clearly, if T is not isomorphic to one of these four graphs above, then T will have a locating coloring such that T has exactly three dominant vertices. By Lemma 2.3, the three dominant vertices must lie in a path. This path must be of length at least 4. By Theorem 3.1, we conclude that T must be a subtree of one of the trees in Figure 2. As a consequence, T is a subtree of either G¹ or G2.

In the following theorems, we will give an infinite number of trees with locating-chromatic number 4 constructed from the trees with locating-chromatic number 3.

Theorem 3.3. Let T ⁰ be a tree constructed from either G¹ or G² by attaching a path of arbitrary length to each vertex. Then, χL(T 0 ) = 4.

Proof. Define a coloring c 0 : V (T 0 ) → {1, 2, 3, 4} such that:

\[c'(u) = c(u)\], for any \(u \in T\),

where c is a coloring on T used in Theorem 3.1, and define the values of c ⁰ on any path L := (w = w0, w1, · · · , wt) attached to a vertex w as follows:

\[c'(w_i) = c(w)\] for even \(i\), and \(c'(w_i) = 4\) for odd \(i\).

We will show that c 0 is a locating-coloring. Let u, v be any two vertices of T ⁰ with c 0 (u) = c 0 (v). If u and v are in T then the color codes are distinct, since their color codes are derived from the previous color codes (under c) by adding the fourth ordinate with entry 1. If u ∈ T and v 6∈ T then d(v, S) > d(u, S), where S is either S1, S² or S3, with Sⁱ being the set of vertices receiving color i under c 0 . Now, let u 6∈ T and v 6∈ T. If u and v are in the same path attached to vertex w then d(u, S) 6= d(v, S) with S being either S1, S² or S3. Now, let u be in a path L¹ attached to w 0 and v be in a path L² attached to w ⁰⁰. If c 0 (w 0 ) = c 0 (w ⁰⁰) then the color codes of u and v are different since the color codes of w 0 and w ⁰⁰ are different. If c 0 (w 0 ) 6= c 0 (w ⁰⁰) then d(u, S) = 1 < d(v, S) with S being the partition class containing vertex w 0 . Therefore, all vertices in T ⁰ have distinct color codes. Thus, c 0 is a locating-coloring on T 0 . Since 4 is the smallest possible number of colors (by Theorem 3.1) then χL(T 0 ) = 4.

Theorem 3.4. Let T ⁰ be a tree constructed in Theorem 3.3. Every subtree of T ⁰ which is not a subtree of G¹ or G² has locating-chromatic number 4.

Proof. A direct consequence of Theorem 3.3.

To conclude this paper, we present an open problem related to the locating-chormatic number of graphs.

Problem 1. Characterize all graphs of order n ≥ 4 with locating-chromatic number 4.

Acknowledgement

The authors are indebted to the anonymous reviewers for their detailed reports. This research was supported by the Directorate General of Higher Education (DGHE), Ministry of Education and Culture, by Research Grant International Research Collaboration and Scientific Publication 082/SP2H/PL/Dit.Litabmas/V/2013.

References

• [1] Asmiati, H. Assiyatun, E.T. Baskoro, Locating-chromatic number of amalgamation of stars, ITB J. Sci. 43A (2011), 1–8.
• [2] Asmiati, E.T. Baskoro, Characterizing all graphs containing cycle with the locating-chromatic number 3, AIP Conf. Proc. 1450 (2012), 351–357.
• [3] Asmiati, E.T. Baskoro, H. Assiyatun, D. Suprijanto, R. Simanjuntak, S. Uttunggadewa, Locating-chromatic number of firecracker graphs, Far East J. Math. Sci. 63:1 (2012), 11– 23.
• [4] E. T. Baskoro, I. A. Purwasih, The locating-chromatic number for corona product of graphs, AIP Conf. Proc. 1450 (2012), 342–345.
• [5] A. Behtoei, B. Omoomi, On the locating chromatic number of Kneser graphs, Discrete Appl. Math. 159 (2011), 2214–2221.
• [6] A. Behtoei, B. Omoomi, On the locating chromatic number of the Cartesian product of graphs, Ars Combin., to appear.
• [7] A. Behtoei, B. Omoomi, The locating chromatic number of the join of graphs, Discrete Appl. Math., to appear.
• [8] G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater, P. Zang , The locating-chromatic number of a graph, Bulls. Inst. Combin. Appl. 36 (2002), 89–101.
• [9] G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater, P. Zang , Graphs of order n with locatingchromatic number n − 1, Discrete Math. 269 (2003), 65–79.