Star-in-coloring of Some Special Graphs

A. Sugumaran and P. Kasirajan

Department of Mathematics, Government Arts College, Tiruvannamalai - 606 603, Tamil Nadu, INDIA.

(Received on: December 18, 2017)


A proper coloring of a graph G = (V, E) is a mapping f:V → N such that if vivj∈E then f(vi) ± f(vj). In this paper we investigate the lower and upper bounds for the star-in-chromatic number of the graphs such as cycle, regular cyclic, gear, fan, double fan, web and complete binary tree. In addition we have given the general coloring pattern of all these graphs and their star-in-chromatic number.
AMS Subject Classification:05C15, 05C20.

Keywords:Coloring, Star-in-coloring, Star-in-chromatic number.


Coloring of graphs is an active research area in graph theory. Many variations of chromatic number of graphs have been studied in literature. The concept of acyclic coloring of graphs was introduced by Grunbaum7, also he introduced the concept of star-coloring of graphs. A graph G is called star-coloring if no path of length three is bicolored. The star- coloring of graphs have been investigated by Fertin, et al.5 and Nesetril, et al.9. A digraph G is said to be in-coloring if any path of length two with end vertices of same color are always directed towards the middle vertex. Motivated through the concepts of star-coloring and in- coloring, Sudha and Kanniga10 have introduced the star-in-coloring graphs. For notation and graph theory terminology we refer to Harary6. Let f = (f, f)be a simple, connected digraph with vertex set f = {c1,v2, ..... , vn } and edge set E, each element of E is a directed edge. An orientation of a graph G is obtained by applying an orientation for each edge e = vivj∈ E either from vi to cjor vitovj. We provide the basic definitions of graph theory which are necessary for our present investigations.

Definition 1.1 A proper coloring of a graph G is a mapping f: V → {1,2,3, ... } such that if e = vivj∈ E, then f(vi) ± f(vj).

Definition 1.2 A graph G is said to be k-colorable if we can assign one of k-colors to each vertex so that adjacent vertices have different colors. If G is k-colorable, but not (k-1) colorable, then we say that the chromatic number of graph G denoted by X (G) is k.

Definition 1.3 A star-coloring of a graph G is a proper coloring of the graph with the condition that no path of length three (P4) is 2-colored. An n-star-coloring of a graph G is a star-coloring of G using at most n colors.

Definition 1.4 An in-coloring of a graph G is a proper coloring of the graph G if there exist any path P3 of length two with the end vertices are of the same color, then the edges of P3 are oriented towards the central vertex.

Definition 1.5 A graph G is said to admit star-in-coloring orientation if it satisfies the following conditions. 1.No path of length three (P4) is bicolored. 2.If any path of length two (P3) with end vertices of same color, then the edges of P3 are directed towards the middle vertex.

Definition 1.6 The minimum number of colors required for the star-in-coloring of a graph G is called the star-in-chromatic number of G and is denoted by Xis(f).

The vertices v1 and v3 are assigned with the color 1, the vertex v4 is assigned with the color 2 and the vertex v2 is assigned with the color 3.
In this graph we see that no two adjacent vertices have the same color, no path on four vertices is bicolored, each and every edge in a path of length two in which end vertices have same color are oriented towards the central vertex. Hence it is star-in-colored with orientation. Further the star-in-chromatic number of the above graph is 3.

Definition 1.7A graph G = (V, E) in which |V| > 3 and maximum number of chords are drawn without form a triangle and the graph is regular, then the graph is called a regular cyclic graph. We denotea regular cyclic graph with p vertices and degree of each vertex n is denoted by RC(p, n).

Definition 1.8 A connected acyclic graph is called a tree. A binary tree is a tree in which only one vertex of degree two and each of the remaining vertices is of degree one or three. A vertex of degree two in a binary tree is called its root vertex. In a binary tree a vertex v is said to be at level l if v is at a distance l from the root vertex.

Definition 1.9 A binary tree with level f is said to be complete if each level f of the binary tree contains exactly 2l vertices, where 0 ≤ l ≤ A. A complete binary tree with level n is denoted by BTn. Note that the complete binary tree BTn contains|V| = 1 + 2 + 22 + ... + 2n vertices and |E| = |V| - 1 edges.


In this section, we have to find the lower and upper bounds of star-in-chromatic number of some of the standard graphs. First we find the upper and lower bounds of star-in- chromatic number of cycle Cn.

From the above cases, we conclude that 3 ≤ Xsi ( Cn ) ≤ 4.

Remark: The star-in-coloring of Cn is not possible, when n is odd. Since if we assign alternate colors for consecutive vertices, we obtain the initial and final vertices are of the same colors. On the other hand, if we assign a new color to the final vertex, then the in-coloring property is not satisfied.

Illustration 2.1.1 The star-in-coloring of cycle C8 is shown in Figure 2.1.1.

The vertices v1,v3, and v5 are assigned the color 1,whereas the vertices v2, v4 and v0 are assigned with colors 2, 3 and 4 respectively.
The star-in-chromatic number of C6 is Xsi(C6) = 4.


Theorem 2.2 The regular cyclic graph RC(p, n) admits star-in-coloring and its star-in- chromaticnumber is n + 1, where p is an even integer and p > 3.

Proof: Consider a regular cyclic graph RC(p, n) which consists of 2n vertices and n2 edges, where n is the degree of the each vertex. Let the vertices be denoted by v1,v2, ... , v2n. Define a function f: V → { 1,2, 3, ... } as follows.

The vertices v1,v3,v5 and v7 are assigned the color 1. The vertices v2 and v6 are assigned the color 2. The vertices v4 and v8 are assigned the color 3. The vertex v0 is assigned the color 4. The star-in-chromatic number of G5 is Xis(G5)=4.

Illustration 2.3.2 Consider a gear graph G4. It consists of 7 vertices and 9 edges. The vertices v1,v3 and v5 are assigned the color 1. The vertices v2,v4,v6 and v0 are assigned the colors 2,3,4 and 5 respectively.


  1. Alon.N, McDiarmid.C, and Reed.B. Acyclic colourings of graphs. Random Structures and Algorithms, 2:277-288, (1990).
  2. Borodin.O.V, Kostochka.A.V, and Woodall.D.R. Acyclic colourings of planar graphswith large girth. J. London Math. Soc., 60 (2):344-352, (1999).
  3. Borodin.O.V, Kostochka.A.V, Raspaud.A, and Sopena.E. Acyclic k-strong coloring of maps on surfaces. Mathematical Notes, 67 (1):29-35, (2000).
  4. Coxter. H. S. M, (1950) Self-dual configurations and regular graphs, Bulletin of the American Mathematical Society, 56, 413-455.
  5. Fertin. G, Raspaud. A, Reed. B, (2001), On star coloring of graphs, Graph Theoretic Concepts in Computer Science, 27th International Workshop, WG 2001, Springer Lecture Notes in Computer Science, 140-153 (2204).
  6. Frank Harary, Graph Theory (Narosa Publishing House, 2001).
  7. Grunbaum. B, Acyclic colorings of planar graphs, Israel J. Math.14, 390-408 (1973).
  8. Kim.D.S, Du.D.Z, and Pardalos.P.M. A coloring problem on the n-cube. Discrete Applied Mathematics, 103:307-311, (2000
  9. Nesetril. J and Ossona de Mendez. P, Colorings and homomorphisms of minor closed classes, Discrete and Computational Geometry: The Goodman Pollack Festschrift (ed. B. Aronov, S. Basu, J. Pach, M. Sharir), Springer Verlag, 651-664 (2003).
  10. Sudha. S and Kanniga. V, Star-in-coloring of Complete bi-partite graphs, Wheel graphs and Prism graphs, International Journal of Engineering and Technology, Vol 2, Issue 2, 97-104 (2014).
map1 map2 map3