Abstract

The purpose of this study is to find the star chromatic number for the central graph, middle graph, total graph and line graph of double star graph K_{1, n, n} denoted by C (K_{1, n, n}), M (K_{1, n, n}), T (K_{1, n, n}) and L (K_{1, n, n}), respectively. We discuss the relationship between star chromatic number with other type of chromatic number such as equitable chromatic number.

---

INTRODUCTION

For a given graph G = (V, E), we do an operation on G by subdividing each edge exactly once and joining all the non adjacent vertices of G. The graph obtained by this process is called central graph (Vernold et al., 2009a, b) of G denoted by C (G). Let G be a graph with vertex set V (G) and edge set E (G). The middle graph (Michalak, 1981) of G denoted by M (G) is defined as follows. The vertex set of M (G) is V (G)∪E (G). About 2 vertices x, y in the vertex set of M (G) are adjacent in M (G) in case one the following holds:

•	x, y are in E (G) and x, y are adjacent in G

•	x is in V (G), y is in E (G) and x, y are incident in G

Let G be a graph with vertex set V (G) and edge set E (G). The total graph (Michalak, 1981; Harary, 1969) of G denoted by T (G) is defined as follows. The vertex set of T (G) is V (G)∪E (G). About 2 vertices x, y in the vertex set of T (G) are adjacent in T (G) in case one the following holds:

•	x, y are in V (G) and x is adjacent to y in G

•	x, y are in E (G) and x, y are adjacent in G

•	x is in V (G), y is in E (G) and x, y are incident in G

The line graph (Harary, 1969) of G denoted by L (G) is the graph with vertices are the edges of G with 2 vertices of L (G) adjacent whenever, the corresponding edges of G are adjacent. Double star K (_{1, n, n}) is a tree obtained from the star K_1,n by adding a new pendant edge of the existing n pendant vertices. It has 2n+1 vertices and 2n edges. The notion of star chromatic number was introduced by Grunbaum (1973). A star coloring (Albertson et al., 2004; Grunbaum, 1973; Fertin et al., 2004) of a graph G is a proper vertex coloring in which every path on four vertices uses at least 3 distinct colors. Equivalently, in a star coloring, the induced subgraphs formed by the vertices of any 2 colors has connected components that are star graphs. The star chromatic number X_s (G) of G is the least number of colors needed to star color G. The notion of equitable coloring was introduced by Meyer (1973).

If the set of vertices of a graph G can be partitioned into k classes V₁, V₂, ...., V_k such that each V_i is an independent set and the condition ||V_i | - | V_j||≤1 holds for every pair (i, j) then G is said to be equitably k-colorable. The smallest integer k for which G is equitable k-colorable is known as the equitable chromatic number (Meyer, 1973) of G and denoted by X = (G).

STAR COLORING ON CENTRAL GRAPH OF DOUBLE STAR GRAPH

Algorithm 1: Input; the number n of K (_{1, n, n}). Output; assigning star coloring for the vertices in C (K_{1, n, n}).

 

Fig. 1:	Double star graph K (1, n, n)

 

 

Fig. 2:	Central graph of double star graph C (K1, n)

 

Theorem 1: For any double star graph K (_{1, n, n}) (Fig. 1 and 2) the star chromatic number is:

Proof: Let v, v₁, v₂, ..., v_n and u₁, u₂, .., u_n be the vertices in K (_{1, n, n}), the vertex v be adjacent to v_i (1≤i≤n). The vertices v_i (1≤i≤n) be adjacent to u_i (1≤i≤n). Let the edge vv_i and uu_i (1≤i≤n) be subdivided by the vertices e_i (1≤i≤n) and s_i (1≤i≤n) in C (K_{1, n, n}). Clearly V [C (K_{1, n, n})] = {v}∪{v_i/1≤i ≤n}∪{ u_i/1≤i≤n}∪{e_i/1≤i≤n}∪{s_i/1≤i≤n}. The vertices v_i (1≤i ≤n) induce a clique of order n (say K_n) and the vertices v, u_i (1≤i≤n) induce a clique of order n+1 (say K_n+1) in C (K_{1, n, n}), respectively also each v_i (1≤i≤n) adjacent to u_j (1≤j≤n), ∀i≠ j. Thus by proper star coloring, we have, X_s [C (K_{1, n, n})]≥2n+1.

Now consider the vertex set V [C (K_{1, n, n})] and the color classes C₁ = {c₁, c₂, c₃, ..., c_n} and C₂ = {c₁, c₂, c₃, ..., c_n, c_n+1}, assign the proper star coloring to C (K_{1, n, n}) by Algorithm 1. Therefore, X_s[C (K_{1, n, n})] ≤2n+1. Hence, X_s[C (K_{1, n, n})] = 2n+1.

STAR COLORING ON MIDDLE AND TOTAL GRAPH OF DOUBLE STAR GRAPH

Algorithm 2: Input; the number n of K (_{1, n, n}). Output; assigning star coloring for vertices in M (K_{1, n, n}) and T (K_{1, n, n}).

Theorem 2: For any double star graph K (_{1, n, n}) (Fig. 3), the star chromatic number is:

Proof: Let V (K_{1, n, n}) = {v}∪{v_i/1≤i≤n}∪{u_i/1≤i≤n }. By definition of middle graph, each edge vv_i and v_iu_i (1≤i≤n) in K (_{1, n, n}) are subdivided by the vertices u_i and s_i in M (K_{1, n, n}), i.e., V [M (K_{1, n, n})] = {v}∪{v_i/1≤i≤n}∪{u_i/1≤i≤n}∪ {e_i/1≤i≤n}∪{s_i/1≤i≤n}, the vertices v, e₁, e₂, ..., e_n induce a clique of order n+1(say K_n+1) in M (K_{1, n, n}). Therefore by proper star coloring, X_s[M (K_{1, n, n})]≥n + 1. Now consider the vertex set V [M (K_{1, n, n})] and colour class C = {c₁, c₂, c₃,.., c_n, c_n+1}, assign the proper star coloring to M (K_{1, n, n}) by Algorithm 2. Thus, we have X_s [M (K_{1, n, n})]≤n+1. Hence, X_s [M (K_{1, n, n})] = n+1.

Theorem 3: For any double star graph K (_{1, n, n}), the star chromatic number is X_s [T (K_{1, n, n})] = n+1.

Proof: Let V (K_{1, n, n}) = {v, v₁, v₂, .., v_n}∪{u₁, u₂, .., u_n} and E (K_{1, n, n}) = {e₁, e₂, ..., e_n}∪{s₁, s₂, s₃,..., s_n}. By the definition of total graph, we have V [T( K_{1, n, n})] = {v} ∪{v_i/1≤i≤n}∪{u_i/1≤i≤n}∪{e_i/1≤i≤n}∪{s_i/1≤i≤n} in which the vertices v, e₁, e₂,...,e_n induce a clique of order n+1 (say K_n+1).

Therefore, by proper star coloring, X_s [T (K_{1, n, n})] ≥n+1. Now consider the vertex set V [T (K_{1, n, n})] and colour class C = {c₁, c₂, c₃, ...c_n, c_n+1}, assign the proper coloring to T (K_{1, n, n}) by: Algorithm 2 (Fig. 4).

 

Fig. 3:	Middle graph of double star graph M (K1, n, n)

 

 

Fig. 4:	Total graph of double star graph T (K1, n, n)

 

Thus, we have X_s [(K_{1, n, n})]≤n+1. Hence, X_s [T (K_{1, n, n})] = n+1.

STAR COLORING ON LINE GRAPH OF DOUBLE STAR GRAPH

Algorithm 3: Input; the number n of K (_{1, n, n}). Output; assigning star coloring for vertices in L (K_{1, n, n}).

Theorem 4: For any double star graph K (_{1, n, n}), the star chromatic number is:

Proof: Let V (K_{1, n, n}) = {v}∪{v_i/1≤i≤n }∪{u_i/1≤i≤n} and E (K_{1, n, n}) = {e₁, e₂, ...e_n}∪{s₁, s₂, s₃, ..., s_n}. By the definition of line graph, each edge of K (_{1, n, n}) taken to be as vertex in L (K_{1, n, n}).

The vertices e₁, e₂, ..., e_n induce a clique of order n in L (K_{1, n, n}), i.e., V [L (K_{1, n, n})] = {e_i/1≤i≤n}∪{s_i/1 ≤I≤n}. Therefore by proper star coloring, X_s [L (K_{1, n, n})]≥n. Now consider the vertex set V [L (K_{1, n, n})] and a color class C = {c₁, c₂, c₃,...c_n}, assign the proper star coloring to L (K_{1, n, n}) by Algorithm 3 (Fig. 5). Thus we have, X_s [L (K_{1, n, n})]≤n. Hence:

 

Fig. 5:	Line graph of double star graph L (K1, n, n)

 

MAIN THEOREM

Theorem 5: For any double star graph K (_{1, n, n}), the equitable chromatic number, X = (C (K_{1, n, n})) = X = (M (K_{1, n, n})) =X = (T (K_{1, n, n})) = n+1.

Now, we characterize the graph for which the star chromatic number and equitable chromatic number are the same. The proof of the main theorem follows from theorem 2, 3, 5 (Vernold and Venkatachalam, 2010).

Theorem 6: For any double star graph K (_{1, n, n}), the star chromatic number and equitable chromatic number, X = (C (K_{1, n, n})) = X = (M (K_{1, n, n})) = X= (T (K_{1, n, n})) = X_s [M (K_{1, n, n})] = X_s [T [K_{1, n, n})] = n+1.

CONCLUSION

In this present study, we have proved for the star chromatic number and the equitable chromatic number are equal for some double star graph families. As a motivation from this study can be extended by classifying the different families of graphs for which these two chromatic numbers are equal.

How to cite this article:

J. Vernold Vivin, N. Mohanapriya and M. Venkatachalam. Star Coloring on Double Star Graph Families.
DOI: https://doi.org/10.36478/jmmstat.2011.33.36
URL: https://www.makhillpublications.co/view-article/1994-5388/jmmstat.2011.33.36