.svg){kind=logo}
A STUDY ON EQUITABLE CHROMATIC AND THRESHOLD OF MYCIELSKIAN OF GRAPHS
Keywords:
Mycielski’s graph, equitable coloring, equitable chromatic number, equitable chromatic threshold.DOI:
https://doi.org/10.17654/0974165823003Abstract
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 $\chi_{=}(G)$, is the minimum $k$ such that $G$ is equitably $k$-colorable. The equitable chromatic threshold of a graph $G$, denoted by $\chi_{=}^*(G)$, is the minimum $t$ such that $G$ is equitably $k$-colorable for $k \geq t$. This paper presents exact values of the equitable chromatic number $\chi_{=}$and equitable chromatic threshold $\chi_{=}^*$ for Mycielski's of some standard graphs.
Received: September 28, 2022;
Accepted: November 15, 2022;
References
Jonathan L. Gross, Jay Yellen and Ping Zhang, Handbook of Graph Theory, Discrete Mathematics and its Applications, CRC Press, New York, 2014.
R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory, Springer Verlag, New York, 2000.
J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, MacMillan, London, UK, 1976.
F. Harary, Graph Theory, Addison-Wesley, Reading, Mass., USA, 1969.
J. Vernold Vivin and K. Kalai Raj, Equitable coloring of Mycielskian of some graphs, Journal of Mathematical Extension 11(3) (2017), 1-18.
J. Clark and D. A. Holton, A First Look at Graph Theory, World Scientific, 1995.
K. Kaliraj, On equitable coloring of Graphs, Ph.D. Thesis, Anna University, Chennai, 2013.
V. Kowsalya and J. Vernold Vivin, A note on acyclic coloring of sunlet graph families, International J. Math. Combin. 1 (2017), 135-138.
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.
W. Meyer, Equitable coloring, Amer. Math. Monthly 80 (1973), 920-922.
Wu-Hsiung Lih and Gerard J. Chang, Equitable coloring of Cartesian products of graphs, Discrete Appl. Math. 160 (2012), 239-247.
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.
Bharati Rajan, Indra Rajasingh and D. Francis Xavier, Harmonious coloring of honeycomb networks, J. Comp. & Math. Sci. 2(6) (2011), 882-887.
P. Erdos, Problem 9, Theory of Graphs and its Application, M. Fielder, ed., Vol. 159, Czech. Acad. Sci. Publ., Prague, 1964.
A. Hajnal and E. Szemeredi, Proof of a conjecture of P. Erdos, P. Erdos, A. Renyi and V. T. Sos, eds., Combinatorial Theory and Applications, North-Holland, London, 1970, pp. 601-623.
H. A. Kiersted and A. V. Kostochka, A short proof of the Hajnal-Szemeredi theorem on equitable coloring, Combin. Probab. Comput. 17(2) (2008), 265-270.
B. L. Chen and K. W. Lih, Equitable coloring of trees, J. Combin. Theory Ser. B 61(1) (1994), 83-87.
H. Furmacnzyk and M. Kubale, The complexity of equitable vertex coloring of graphs, Journal of Applied Computer Science 13(2) (2005), 95-107.
H. L. Bodlaender and F. V. Fomin, Equitable colorings of bounded treewidth graphs, Theoret. Comput. Sci. 349(1) (2005), 22-30.
K.-W. Lih and P.-L. Wu, On equitable coloring of bipartite graphs, Discrete Math. 151(1-3) (1996), 155-160.
H. P. Yap and Y. Zhang, The equitable coloring conjecture holds for outerplanar graphs, Bull. Inst. Math. Acad. Sinica 25 (1997), 143-149.
H. P. Yap and Y. Zhang, Equitable colorings of planar graphs, J. Combin. Math. Combin. Comput. 27 (1998), 97-105.
W. Wang and K. Zhang, Equitable colorings of line graphs and complete r-partite graphs, Systems Science and Mathematical Sciences 13 (2000), 190-194.
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.
Downloads
Published
Issue
Section
License
Copyright (c) 2022 Pushpa Publishing House, Prayagraj, India
This work is licensed under a Creative Commons Attribution 4.0 International License.
_________________________
Attribution: Credit Pushpa Publishing House as the original publisher, including title and author(s) if applicable.
Contact Pushpa Publishing House for more info or permissions.
Journal Impact Factor: 
