A proper vertex coloring of a graph G is equitable if the sizes of any two color classes differ by at most one. The equitable chromatic number of a graph G, denoted by  is the minimum k such that G is equitably k-colorable. The equitable chromatic threshold of a graph G, denoted by  is the minimum t such that G is equitably k-colorable for  This paper presents exact values of the equitable chromatic number  and equitable chromatic threshold  for Mycielski’s of some standard graphs.

Mycielski’s graph, equitable coloring, equitable chromatic number, equitable chromatic threshold.

Received: September 28, 2022; Accepted: November 15, 2022; Published: December 16, 2022

How to cite this article: Loura Jency and Benedict Michael Raj, A study on equitable chromatic and threshold of Mycielskian of graphs, Advances and Applications in Discrete Mathematics 36 (2023), 35-54. http://dx.doi.org/10.17654/0974165823003

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:

[1] Jonathan L. Gross, Jay Yellen and Ping Zhang, Handbook of Graph Theory, Discrete Mathematics and its Applications, CRC Press, New York, 2014.
[2] R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory, Springer Verlag, New York, 2000.
[3] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, MacMillan, London, UK, 1976.
[4] F. Harary, Graph Theory, Addison-Wesley, Reading, Mass., USA, 1969.
[5] J. Vernold Vivin and K. Kalai Raj, Equitable coloring of Mycielskian of some graphs, Journal of Mathematical Extension 11(3) (2017), 1-18.
[6] J. Clark and D. A. Holton, A First Look at Graph Theory, World Scientific, 1995.
[7] K. Kaliraj, On equitable coloring of Graphs, Ph.D. Thesis, Anna University, Chennai, 2013.
[8] V. Kowsalya and J. Vernold Vivin, A note on acyclic coloring of sunlet graph families, International J. Math. Combin. 1 (2017), 135-138.
[9] S. K. Vaidya and Rakhimol V. Issac, Equitable coloring of some path related graphs, IOSR Journal of Mathematics 12(5) Ver. VIII (2016), 65-69.
[10] W. Meyer, Equitable coloring, Amer. Math. Monthly 80 (1973), 920-922.
[11] Wu-Hsiung Lih and Gerard J. Chang, Equitable coloring of Cartesian products of graphs, Discrete Appl. Math. 160 (2012), 239-247.
[12] K. W. Lih, The equitable coloring of graphs, D. Z. Du and P. M. Pardalos, eds., Handbook of Combinatorial Optimization, Kluwer, Dordrecht, Vol. 3, 1998, pp. 543-566.
[13] Bharati Rajan, Indra Rajasingh and D. Francis Xavier, Harmonious coloring of honeycomb networks, J. Comp. & Math. Sci. 2(6) (2011), 882-887.
[14] P. Erdős, Problem 9, Theory of Graphs and its Application, M. Fielder, ed., Vol. 159, Czech. Acad. Sci. Publ., Prague, 1964.
[15] A. Hajnal and E. Szemerédi, Proof of a conjecture of P. Erdős, P. Erdős, A. Rényi and V. T. Sós, eds., Combinatorial Theory and Applications, North-Holland, London, 1970, pp. 601-623.
[16] H. A. Kiersted and A. V. Kostochka, A short proof of the Hajnal-Szemerédi theorem on equitable coloring, Combin. Probab. Comput. 17(2) (2008), 265-270.
[17] B. L. Chen and K. W. Lih, Equitable coloring of trees, J. Combin. Theory Ser. B 61(1) (1994), 83-87.
[18] H. Furmacńzyk and M. Kubale, The complexity of equitable vertex coloring of graphs, Journal of Applied Computer Science 13(2) (2005), 95-107.
[19] H. L. Bodlaender and F. V. Fomin, Equitable colorings of bounded treewidth graphs, Theoret. Comput. Sci. 349(1) (2005), 22-30.
[20] K.-W. Lih and P.-L. Wu, On equitable coloring of bipartite graphs, Discrete Math. 151(1-3) (1996), 155-160.
[21] H. P. Yap and Y. Zhang, The equitable -coloring conjecture holds for outerplanar graphs, Bull. Inst. Math. Acad. Sinica 25 (1997), 143-149.
[22] H. P. Yap and Y. Zhang, Equitable colorings of planar graphs, J. Combin. Math. Combin. Comput. 27 (1998), 97-105.
[23] W. Wang and K. Zhang, Equitable colorings of line graphs and complete r-partite graphs, Systems Science and Mathematical Sciences 13 (2000), 190-194.
[24] S. Nada, A. Elrokh, E. A. Elsakhawi and D. E. Sabra, The corona between cycles and paths, J. Egyptian Math. Soc. 25 (2017), 111-118.