ON SUM EDGE-COLORINGS OF COMPLETE TRIPARTITE GRAPHS

Hamlet V. Mikaelyan

doi:10.46991/PYSUA.2025.59.3.069

Authors

Hamlet V. Mikaelyan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia https://orcid.org/0009-0006-9642-7667

DOI:

https://doi.org/10.46991/PYSUA.2025.59.3.069

Keywords:

edge-coloring, sum edge-coloring, edge-strength

Abstract

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.

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