Twin Edge Coloring of Mycielski Graph of Some Families of Graph
DOI:
https://doi.org/10.5281/zenodo.21899563Keywords:
Twin edge coloring, Twin chromatic index, Mycielski graph, graph invariantsAbstract
Twin edge coloring is a proper edge coloring in which the vertex coloring induced by the sum of the colors assigned to incident edges is also proper. The research aimed to define and construct the Mycielski graph of a given graph, examine its fundamental structural properties, and determine the twin chromatic index of the Mycielski graphs of paths, cycles, stars, and tadpole graphs. Using a mathematical and expository research approach, the study applied established concepts and results in graph theory to analyze the structural characteristics and edge-coloring behavior of these graph families under the Mycielski construction. The findings revealed important properties of Mycielski graphs, including their order, size, degree, radius, diameter, girth, and circumference, and established results on the twin edge coloring and twin-chromatic indices of the selected graph families. The analysis demonstrated that the structural modifications introduced by the Mycielski construction significantly affect twin edge coloring behavior. Consequently, the study concluded that Mycielski graphs provide a valuable framework for investigating twin edge coloring and related graph coloring parameters. The results advance twin edge coloring theory and lay foundation for future research on Mycielskian graphs and other graph coloring problems.
Downloads
References
Abedin, P., Akbari, S., Demange, M., & Ekim, T. (2017). Complexity of the improper twin edge coloring of graphs. Graphs and Combinatorics, 33(4), 595–615. https://doi.org/10.1007/s00373-017-1782-7
Abramowitz, M., & Stegun, I. A. (Eds.). (1964). Handbook of mathematical functions with formulas, graphs, and mathematical tables (Applied Mathematics Series No. 55). National Bureau of Standards. https://doi.org/10.6028/NBS.AMS.55
Anantharaman, S. (2020). Twin edge coloring of total graph and graphs with twin chromatic index Δ + 2. Applications and Applied Mathematics: An International Journal, 15(1), Article 18.
Andrews, E., Helenius, L., Johnston, D., VerWys, J., & Zhang, P. (2014). On twin edge colorings of graphs. Discussiones Mathematicae Graph Theory, 34(3), 613–627. https://doi.org/10.7151/dmgt.1756
Bondy, J. A., & Murty, U. S. R. (2008). Graph theory. Springer.
Chartrand, G., & Zhang, P. (2009). Chromatic graph theory. Chapman & Hall/CRC. https://doi.org/10.1201/9781584888017
Chvátal, V. (1974). The minimality of the Mycielski graph. In R. A. Bari & F. Harary (Eds.), Graphs and combinatorics(Lecture Notes in Mathematics, Vol. 406, pp. 243–246). Springer. https://doi.org/10.1007/BFb0066446
Diestel, R. (2017). Graph theory (5th ed.). Springer. https://doi.org/10.1007/978-3-662-53622-3
Došlić, T. (2005). Mycielskians and matchings. Discussiones Mathematicae Graph Theory, 25(3), 261–266. https://doi.org/10.7151/dmgt.1279
Fisher, D. C., McKenna, P. A., & Boyer, E. D. (1998). Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski’s graphs. Discrete Applied Mathematics, 84(1–3), 93–105. https://doi.org/10.1016/S0166-218X(97)00126-1
Harary, F. (1969). Graph theory. Addison-Wesley.
Jensen, T. R., & Toft, B. (1995). Graph coloring problems. Wiley-Interscience.
Lin, W., Wu, J., Lam, P. C. B., & Gu, G. (2006). Several parameters of generalized Mycielskians. Discrete Applied Mathematics, 154(8), 1173–1182. https://doi.org/10.1016/j.dam.2005.11.001
Mycielski, J. (1955). Sur le coloriage des graphes. Colloquium Mathematicae, 3(2), 161–162. https://doi.org/10.4064/cm-3-2-161-162
Rajarajachozhan, R., & Sampathkumar, R. (2016). Twin edge colorings of certain square graphs and product graphs. Electronic Journal of Graph Theory and Applications, 4(1), 79–93. https://doi.org/10.5614/ejgta.2016.4.1.7
Tolentino, J. D. (2019). On the twin chromatic indices of trees and some graphs with maximum degree 3 (Doctoral dissertation, Ateneo de Manila University).
Tolentino, J. D., Marcelo, R. M., & Tolentino, M. A. C. (2020). Twin chromatic indices of some graphs with maximum degree 3. Journal of Physics: Conference Series, 1538(1), Article 012004. https://doi.org/10.1088/1742-6596/1538/1/012004
Tolentino, J. D. L., Marcelo, R. M., & Tolentino, M. A. C. (2022). On twin edge colorings in m-ary trees. Electronic Journal of Graph Theory and Applications, 10(1), 131–149. https://doi.org/10.5614/ejgta.2022.10.1.8
West, D. B. (2001). Introduction to graph theory (2nd ed.). Prentice Hall.
Yap, H. P. (1996). Total colourings of graphs (Lecture Notes in Mathematics, Vol. 1623). Springer. https://doi.org/10.1007/BFb0092895
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
How to Cite
