On equitable chromatic number of Tadpole graph T_{m,n}

Abstract

Graph coloring is a special case of graph labeling. Proper vertex k-coloring of a graph Gis to color all the vertices of a graph with different colors in such a way that no two adjacent vertices are assigned with the same color. In a vertex coloring of G, the set of vertices with the same color is called color class. An equitable k-coloring of a graph G is a proper k-coloring in which any two color classes differ in size by atmost one. In this paper we give results regarding the equitable coloring of central, middle, total and line graphs of Tadpole graph which is obtained by connecting a cycle graph and a path graph with a bridge.

Keywords

• Equitable coloring,Tadpole graph,cycle graph,path graph,middle graph,total graph,central graph,line graph

References

1. Akbar, Ali M.M. and Vernold, Vivin J., Harmonious chromatic number of central graph of complete graph families, Journal of Combinatorics Information and System Sciences, Vol.32, No 1-4 (Combined), (2007).
2. Akbar, Ali M.M, Kaliraj, K., and Vernold, Vivin J., On equitable coloring of central graphs and total graphs, Electronic notes in Discrete Mathematics, 33, (2009).
3. Bondy, J.A. and Murty, U.S.R., Graph theory with Applications, London, MacMillan, 1976.
4. Chen, B.L. and Lin, K.W., A note on the m--bounded chromatic number of a tree, Eur. J. Combia. 14(1994).
5. Furmanczyk, H., Equitable coloring of Graph products, Opuscula Mathematica, Vol 26. No.1, (2006).
6. Furmanczyk, H., Jastrzebski A, Kubale M, Equitable coloring of graphs, Recent theoretical results and new practical Algorithms.
7. Hajnal, A., Szemeredi E., Proof of a conjecture of Endos, in: Combinatorial theory and its applications, Colloq. Math. Soc. Janos Bolyai, North - Holland, Amsterdam, Vol - 4, II, (1970), 601 - 623.
8. Hansen, P., Hertz A, and Kuplinsky J, Bounded vertex colorings of graphs, Discrete Math 111, (1993).

9. Meyer, W., Equitable coloring, Amer. Math. Monthly, 80, (1973).
10. Yan, Z., Wang, W., Equitable chromatic threshold of complete multipartite graphs, Combinatorics, (2012).