** Open Journal of Discrete Mathematics** Vol.1 No.2(2011), Article ID:5742,4 pages DOI:10.4236/ojdm.2011.12010

b-Chromatic Number of

^{1}Department of Maths CA, Kongunadu Arts & Science College, Coimbatore, India

^{2}Department of Mathematics, Kongunadu Arts & Science College, Coimbatore, India

^{3}Department of Mathematics, Indus College of Engineering, Coimbatore, India

E-mail: vijikasc@gmail.com, ktmaths@yahoo.com, roopeshsha@gmail.com

Received April 2, 2011; revised May 2, 2011; accepted May 15, 2011

**Keywords:** chromatic number, b-chromatic, b-colouring, Middle graph

Abstract

In this paper, we discuss about the b-colouring and b-chromatic number for middle graph of Cycle, Path, Fan graph and Wheel graph denoted as.

1. Introduction

Let G be a finite undirected graph with no loops and multiple edges. A coloring (i.e., proper coloring) of a graph G = (V,E) is an assignment of colors to the vertices of G, such that any two adjacent vertices have different colors. A coloring is called a b-coloring [1], if for each color i there exists a vertex x_{i} of color i such that every color j ≠ i, there exists a vertex y_{j} of color j adjacent to x_{i}, such a vertex x_{i} is called a dominating vertex for the colour class i or color dominating vertex which is known as b-chromatic vertex.

The b-chromatic number of a graph G, denoted by j(G) is the largest positive integer k such that G has a b-colouring by k colors. The b-chromatic number of a graph was introduced by R.W. Irwing and manlove [2] in the year 1999 by considering proper colorings that are minimal with respect to a partial order defined on the set of all partitions of V(G). They proved that determining j(G)[3] is NP-hard for general graphs, but polynomial for trees.

Let G be a graph with vertex set V(G) and the edge set E(G). The middle graph [4,5] of G, denoted by M(G) is defined as follows. The vertex set of M(G) is defined as follows. The vertex set of M(G) is V(G) È E(G). Two vertices x, y in the vertex set of M(G) are adjacent in M(G) in case one of the following holds;

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

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

2. b-Chromatic Number of Middle Graph of Cycle

2.1. Definition of Cycle

A Cycle is a circuit in which no vertex except the first (which is also the last) appears more than once. A cycle with n vertices is denoted by Cn.

2.2. Theorem

For any n ≥ 3, j[M(Cn)] = n.

Proof

Let C_{n} be a cycle of length n with the vertices V_{1}, V_{2}, , V_{n}. By the definition of middle graph the edge V_{ij} for 1 ≤ i ≤ n, 1 ≤ j ≤ n of the cycle C_{n} is subdivided by the vertex for m = 1, 2, , n. Here the vertices, V_{i} induces a clique of order n.

Now assign a proper colouring to these vertices as follows. Consider a colour class C = {c_{1}, c_{2}, c_{3}, , c_{n}}. Assign the color c_{i} to the vertex for i = 1, 2, , n. Here M(C_{n}) contains a clique of order n, so for proper colouring we require maximum n colours to colour the vertices of, which produces a b-chromatic coloring. Next we assign a colouring to the vertices V_{i} for i = 1, 2, , n. Suppose if we assign any new colour c_{n+1} to the vertex V_{i} i = 1, 2, , n, it will not produce a b-chromatic colouring because none of the vertices v_{i} does not realizes its own colours. Therefore the only possibility is to assign an existing colors to the vertices v_{i}.

(a)(b)

Figure 1. (a) [C_{5}]; (b) j{M(C_{5})} = 5.

Hence by colouring procedure the above said colouring is maximal and b-chromatic.

3. b-Chromatic Number of Middle Graph of Path

3.1. Definition of Path

A Path is a sequence of consecutive edges in a graph and the length of the path is the number of edges traversed. A path with n vertices is denoted as P_{n}.

3.2. Theorem

For any n ≥ 2,

Proof

Let P_{n} be any path of length n – 1 with vertices v_{1}, v_{2}, , v_{n}._{ }By the definition of middle graph each edge of v_{ij}_{ }for 1 ≤ i ≤ n, 1 ≤ j ≤ n of the path graph P_{n} is subdivided by the vertex in M[P_{n}] and the vertices along with induces a clique of order n in M[P_{n}].

i.e.,

Now consider a proper colouring to M[P_{n}] as follows. Consider the colour class. Assign the color c_{i} to the vertices for i = 1, 2, , n. Here M[P_{n}] contains a clique of order n. So for proper colouring it require n distinct colours which results in b-chromatic coloring. Next we assign the coloring to the vertices v_{i} for i = 1, 2, , n. Suppose if we assign the colour c_{n}_{+1} to the vertex v_{i} i =n which does not produces b-coloring. Hence we should assign only an existing colours to the vertices. Hence by coloring procedure it is the maximal and b-chromatic coloring.

(a)(b)

Figure 2. (a) P_{3}; (b) j[M(P_{3})] = 3.

.

4. b-Chromatic Number of Midlle Graph of Fan Graph

4.1. Definition of Fan Graph

A fan graph F_{m}_{,n} is defined as the graph join, where is the empty graph on nodes and is the path on n nodes.

4.2. Theorem

Proof

Let (x,y) be the bipartition of F_{m}_{,n} with |x| = m and |y| = n. Let V be the only vertex of x and y = {v, v_{2}, , v_{n}}. By the definition of Middle graph each edge vv_{i} for i = 1, 2, 3, , n of F_{1,n} is subdivided by the vertex in M[F_{1,n}] and the vertices, v induces a clique of order n + 1 in M[F_{1,n}].

i.e.,.

Now assign a proper colouring to these vertices as follows. Consider a colour class C = {c_{1}, c_{2}, , c_{n}_{+1}}. First assign the colour c_{1}, c_{2}, , c_{n} to the vertices for m = 1, 2, , n. Here M[F_{1,n}] contains a clique of order n. So for proper colouring we require n distinct colours which results as b-chromatic colouring. Next assign the colour to the vertex v and to the vertices. Here the vertex v realizes its own colors but the vertices does not realizes its own colors, so we cannot assign any new colours to the vertices for i = 1, 2, , n. Therefore by assigning only existing colors to the v_{i} produces a b-chromatic coloring. Hence by coloring procedure the above said col-

(a)(b)

Figure 3. (a) [F_{1,3}]; (b) j[M(F_{1,3})] = 4.

oring is maximal.

.

5. b-Chromatic Number of Middle Graph of Wheel Graph

5.1. Definition of Wheel Graph

A graph W_{n} of order n which contains a cycle of order n − 1, and for which every graph vertex in the cycle is connected to one other graph vertex (which is known as hub). The edges of a wheel which include the hub are spokes.

5.2. Theorem

For any n > 4, j[M(W_{n})] = n

Proof

Let be the vertices taken in anticlock wise direction in the wheel graph w_{n}, where v_{n} is the hub. In M(w_{n}), by the definition of middle graph the edge incident with v_{i} together with vertex v_{i} induces a clique of n vertices in M(w_{n}). Let be the clique in M(w_{n}) for i = 1, 2, , n.

Now consider a proper colouring to these vertices as follows. Consider the color class. First assign the color to the vertex for i = 1, 2, , n. By the above statement that M(w_{n}) contains a clique of order n, so we need only n colors to colour the vertices. Next we assign the color c_{n}_{+1} to the hub. Here the vertices and the hub v_{n} realizes its colors, which produces a b-chromatic coloring. Next if we assign any new color to the vertices v_{i} for i = 1, 2, , n − 1, it will not produce a b-chromatic coloring. So we should assign the existing colors c_{n}_{+1} to the vertices v_{i} for i = 1, 2, , n−2 and c_{1} to the verter v_{n}_{−1}. Hence by coloring procedure it is the maximum and b-chromatic coloring.

(a)(b)

Figure 4. (a) [w_{5}]; (b) j[M(w_{5})] = 5.

6. References

[1] S. Corteel, M. Valencia-Pabon and J.-C. Vera, “On Aproximating the b-chromatic Number,” Discrete Applied Mathematics, Vol. 146, No. 1, 2005, pp. 106-110. doi:10.1016/j.dam.2004.09.006

[2] R. W. Irving and D. F. Manlove, “The b-chromatic Number of a Graph,” Discrete Applied Mathematics, Vol. 91, No. 1, 1999, pp. 127-141. doi:10.1016/S0166-218X(98)00146-2

[3] M. Kouider, “b-chromatic Number of a Graph,” Subgraphs and Degrees Rappor interne LRI 1392.

[4] V. J. Vernold, M. Venkatachalam and A. M. M. Akbar “A Note on Achromatic Coloring of Star Graph Families,” Filomat, Vol. 23, No. 3, 2009, pp. 251-255. doi:10.2298/FIL0903251V

[5] K. Thilagavathi and N. Roopesh, “Generalization of Achromatic Colouring of Central Graphs,” Electronic Notes in Discrete Mathematics, Vol. 33, 2009, pp. 147-152. doi:10.1016/j.endm.2009.03.021

[6] V. J. Vernold and A. M.M. Akbar, “On Harmonious Coloring of Middle Graph of C(Cn),C(K1,n) and C(Pn),” Note di Matematica, Vol. 29, No. 2, 2009, pp. 201-211.

[7] H. Hajiabolhassan, “On the b-chromatic Number of Kneser Graphs,” Discrete Applied Mathematics, Vol. 158, No. 3, 2010, pp. 232-234. doi:10.1016/j.dam.2009.09.023

[8] B. Effantin, “The b-chromatic Number of power Graphs of Complete Caterpillars,” The Journal of Discrete Mathematical Sciences & Cryptography, Vol. 8, 2005, pp. 483-502.

[9] C. T. Hoang and M. Kouider, “On the B-Dominating Colouring of Graphs,” Discrete Applied Mathematics, Vol. 152, No.1-3, 2005, pp. 176-186. doi:10.1016/j.dam.2005.04.001