ON SUM EDGE-COLORINGS OF COMPLETE TRIPARTITE GRAPHS
DOI:
https://doi.org/10.46991/PYSUA.2025.59.3.069Keywords:
edge-coloring, sum edge-coloring, edge-strengthAbstract
A proper edge-coloring of a graph is called a sum edge-coloring if it minimizes the total sum of colors on all the edges of the graph. The aforementioned minimal sum is called the edge-chromatic sum of the graph, and the minimal number of colors needed for a sum edge-coloring is called the edge-strength of the graph. In this paper, upper bounds on the values of the edge-chromatic sums of some complete tripartite graphs are given, while for some other complete tripartite graphs, the exact values of both parameters are obtained.
Downloads
References
Supowit K.J. Finding a Maximum Planar Subset of a Set of Nets in a Channel. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 6 (1987), 93-94. https://doi.org/10.1109/TCAD.1987.1270250
Kubicka E. The Chromatic Sum of a Graph. Western Michigan University (1989).
Bar-Noy A., Bellare M., et al. On Chromatic Sums and Distributed Resource Allocation. Inform. and Comput. 140 (1998), 183-202. https://doi.org/10.1006/inco.1997.2677
Salavatipour M.R. On Sum Coloring of Graphs. Discrete Appl. Math. 127 (2003), 477-488. https://doi.org/10.1016/S0166-218X(02)00249-4
Giaro K., Kubale M. Edge-Chromatic Sum of Trees and Bounded Cyclicity Graphs. Inform. Process. Lett. 75 (2000), 65-69. https://doi.org/10.1016/S0020-0190(00)00072-7
Petrosyan P.A., Kamalian R.R. On Sum Edge-Coloring of Regular, Bipartite and Split Graphs. Discrete Appl. Math. 165 (2014), 263-269. https://doi.org/10.1016/j.dam.2013.09.025
Hajiabolhassan H., Mehrabadi M.L., Tusserkani R. Minimal Coloring and Strength of Graphs. Discrete Math. 215 (2000), 265-270. https://doi.org/10.1016/S0012-365X(99)00319-2
Cardinal J., Ravelomanana V., Valencia-Pabon M. Chromatic Edge Strength of Some Multigraphs. Electron. Notes Discrete Math. 30 (2008), 39-44. https://doi.org/10.1016/j.endm.2008.01.008
West D.B. Introduction to Graph Theory. Prentice-Hall, New Jersey (2001). https://dwest.web.illinois.edu/igt/
Hoffman D.G., Rodger C.A. The Chromatic Index of Complete Multipartite Graphs. J. Graph Theory 16 (1992), 159-163. https://api.semanticscholar.org/CorpusID:29985008
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Proceedings of the YSU
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
