No Access

b-Chromatic Sum and b-Continuity Property of Some Graphs

Department of Mathematics, School of Advanced Sciences (SAS), VIT-AP University, Amaravati, Andhra Pradesh 522237, India

E-mail Address: lisnapc@gmail.com

Search for more papers by this author

and

M. S. Sunitha

Department of Mathematics, National Institute of Technology, Calicut – 673 601, India

E-mail Address: sunitha@nitc.ac.in

Search for more papers by this author

https://doi.org/10.1142/S0219265921500122Cited by:1 (Source: Crossref)

Abstract

A b-coloring of a graph $G$ $G$ is a proper coloring of the vertices of $G$ $G$ such that there exist a vertex in each color class joined to at least one vertex in each other color classes. The b-chromatic number of a graph $G$ $G$ , denoted by $φ (G)$ $φ (G)$ , is the largest integer $k$ $k$ such that $G$ $G$ has a b-coloring with $k$ $k$ colors. The b-chromatic sum of a graph $G (V, E)$ $G (V, E)$ , denoted by $φ^{'} (G)$ , is introduced and it is defined as the minimum of sum of colors $c (v)$ of $v$ for any $v \in V$ in a b-coloring of $G$ using $φ (G)$ colors. A graph $G$ is b-continuous, if it admits a b-coloring with $t$ colors, for every $t = χ (G), \dots, φ (G)$ . In this paper, the $b$ -continuity property of corona of two cycles, corona of two star graphs and corona of two wheel graphs with unequal number of vertices is discussed. The b-continuity property of corona of any two graphs with same number of vertices is also discussed. Also, the b-continuity property of Mycielskian of complete graph, complete bipartite graph and paths are discussed. The b-chromatic sum of power graph of a path is also obtained.

Keywords:

AMSC: 05C15

References

1. F. Bonomo, G. Duran, F. Maffray, J. Marenco and M. Valencia-Pabon , On the b-coloring of cographs and $P_{4}$ -sparse graphs, Graphs Combin. 25 (2009) 153–157. Crossref, Web of Science, Google Scholar
2. D. Gaceb, V. Eglin, F. Lebourgeois and H. Emptoz , Graph b-coloring for automatic recognition of documents, in Proceedings of ICDAR’09 (2009), pp. 261–265. Crossref, Google Scholar
3. B. Effantin and H. Kheddouci , The b-chromatic number of some power graphs, Discr. Math. Theoret. Comput. Sci. 6 (2003) 0045–0054. Web of Science, Google Scholar
4. A. El Sahili and M. Kouider , About b-Coloring of Regular Graphs, Res. Rep. 1432, LRI, Univ. Orsay, France (2006). Google Scholar
5. H. Elghazel, T. Yoshida, V. Deslandres, M. S. Hacid and A. Dussauchoy , A new greedy algorithm for improving b-coloirng clustering, in Proceedings of GbR2007 (2007), pp. 228–239. Google Scholar
6. G. Chartrand and P. Zhang , Chromatic Graph Theory (CRC Press, 2009). Google Scholar
7. F. Harary , Graph Theory (Addison-Wesley, 1969). Crossref, Google Scholar
8. F. Buckley and F. Hararry , Distance in Graphs (Addison Wesley, 1990). Google Scholar
9. R. W. Irving and D. F. Manlove , The b-chromatic number of a graph, Discrete Appl. Math. 91(1–3) (1999) 127–141. Crossref, Web of Science, Google Scholar
10. I. Gonzalez Yero, D. Kuziak and A. Rondon Aguilar , Coloring, location and domination of corona graphs, Aequationes Mathematicae 86(1–2) (2013) 1–21. Crossref, Web of Science, Google Scholar
11. R. Javadi and B. Omoomi , On b-coloring of the Kneser graphs, Discrete Math. 309, (2009) 4399–4408. Crossref, Web of Science, Google Scholar
12. P. C. Lisna and M. S. Sunitha , b-Chromatic sum of a graph, Discr. Math. Algorithms Appl. 7(3) (2015) 1550040-1–15. Google Scholar
13. P. C. Lisna and M. S. Sunitha , A note on the b-chromatic number of corona of graphs, J. Interconnection Networks 15(1&2) (2015) 1550004-1–14. Web of Science, Google Scholar
14. P. C. Lisna and M. S. Sunitha , The b-chromatic number of Mycielskian of some graphs, Int. J. Convergence Comput. 2(1) (2016) 23–40. Crossref, Google Scholar
15. J. Mycielski , Sur le coloriage des graphs, Colloq. Math. 3 (1955) 161–162. Crossref, Google Scholar
16. S. Cabello and M. Jacovac , On the b-chromatic number of regular gtaphs, Discrete Appl. Math. 159(3) (2011) 1303–1310. Crossref, Web of Science, Google Scholar
17. T. Yaoshid, H. Elghazel, V. Deslandres, M.-S. Hacid and A. Dussauchoy , Towards improving b-coloring based clustering using a greedy re-coloring algorithm, Advances in Greedy Algorithms, W. Bednorz (ed.) (2008), pp. 553–568. Crossref, Google Scholar
18. M. Venkatachalam and J. Vernold Vivin , About b-coloring of Windmill graph, Proceedings of the National Academy of Sciences, India Section A: Physical Sciences 83(3) (2013) 253–255, https://doi.org/10.1007/s40010-013-0074-8. Crossref, Web of Science, Google Scholar
19. M. Venkatachalam and J. Vernold Vivin , Discussion on b-chromatic number with other types of chromatic numbers on double star graphs, Ricerche di Mathematica, Vol. 63 (Springer, 2014), pp. 295–305. Google Scholar
20. J. Vernold Vivin and M. Venkatachalam , A note on b-coloring of fan graphs, Journal of Discr. Math. Sci. Cryptography-Taylor and Francis 17(5–6) (2014) 443–448. Google Scholar
21. J. Vernold Vivin and M. Venkatachalam , On b-chromatic number of Sun let graph and wheel graph families, J. Egyptian Mathematical Society (2014), http://dx.doi.org/10.1016/j.joems.2014.05.011. Google Scholar
22. J. Vernold Vivin and M. Venkatachalam , The b-chromatic number of corona graphs, Utilitas Mathematica 88 (2012) 299–307. Web of Science, Google Scholar
23. D. Vijayalakshmi and K. Thilagavathi , b-coloring in the context of some graph operations, Int. J. Mathematical Archive 3(4) (2012) 1439–1442. Google Scholar
24. D. Vijayalakshmi and K. Thilagavathi , A note on b-chromatic number of the transformation graph $G^{+ + -}$ and corona product of graphs, Int. J. Appl. Math. Res. 1(4) (2012) 715–725. Google Scholar
25. W.-H. Lin and G. J. Chang , b-chromatic numbers of powers of paths and cycles, Discr. Appl. Math. 161 (2013) 2532–2536. Crossref, Web of Science, Google Scholar