ON EDGE-CHROMATIC SUMS OF CORONA PRODUCTS OF GRAPHS
DOI:
https://doi.org/10.46991/PYSUA.2026.60.2.083Keywords:
edge-coloring, edge-chromatic sum, sum edge-coloringAbstract
A proper edge-coloring of a graph $G$ is a mapping from its edges to the set of positive integers, so that adjacent edges receive different numbers (colors). If a proper edge-coloring of a graph $G$ minimizes the sum of colors on all edges, it is called a sum edge-coloring and the sum is called the edge-chromatic sum of $G$. In this paper, we study the connection between the edge-chromatic sum of corona product of graphs with the edge-chromatic sums of its factors. We provide general upper bounds on the edge-chromatic sum of corona products of graphs, as well as we prove that the edge-chromatic sum of the corona products of bipartite graphs and regular graphs of odd order can be exactly determined by the edge-chromatic sums of the factors.
Downloads
References
West D.B. Introduction to Graph Theory. Prentice-Hall, New Jersey (2001). https://dwest.web.illinois.edu/igt/
Supowit K.J. Finding a Maximum Planar Subset of a Set of Nets in a Channel. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 6 (1987), 93-94. https://doi.org/10.1109/TCAD.1987.1270250
Kubicka E. The Chromatic Sum and Efficient Tree Algorithms. PhD Thesis. Western Michigan University (1989).
Giaro K., Janczewski R., et al. A 27/26-approximation Algorithm for the Chromatic Sum Coloring of Bipartite Graphs. Lecture Notes in Computer Science. 2462 (2002), 135-145. https://doi.org/10.1007/3-540-45753-4_13
Jansen K. The Optimum Cost Chromatic Partition Problem. Algorithms and Complexity. Springer, Berlin (1997), 25-36.
Kubicka E., Kubicki G., Kountanis D. Approximation Algorithms for the Chromatic Sum. In: Lecture Notes in Comput. Sci. 507 (1991), 15-21. https://doi.org/10.1007/BFb0038467
Malafiejski M., Giaro K., et al. Sum Coloring of Bipartite Graphs with Bounded Degree. Algorythmica 40 (2004), 235-244. https://doi.org/10.1007/s00453-004-1111-4
Thomassen C., Erdos P., et al. Tight Bounds on the Chromatic Sum of a Connected Graph. J. Graph Theory 13 (1989), 353-357. https://doi.org/10.1002/jgt.3190130310
Lecat C., Lucet C., Li C.-M. New Lower Bound for the Minimum Sum Coloring Problem. In: Proc. AAAI Conf. Artificial Intelligence (2017), 853-859. https://doi.org/10.1609/aaai.v31i1.10661
Moukrim A., Sghiouer K. et al. Upper and Lower Bounds for the Minimum Sum Coloring Problem. International Symposium on Combinatorial Optimization (ISCO2010) (2013).
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
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
Marx D. Complexity Results for Minimum Sum Edge Coloring. Discrete Appl. Math. 157 (2009), 1034-1045. https://doi.org/10.1016/j.dam.2008.04.002
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.bf 165 (2014), 263-269. https://doi.org/10.1016/j.dam.2013.09.025
Mitchem J., Morriss P., Schmeichel E.F. On the Cost Chromatic Number of Outerplanar, Planar, and Line Graphs. Discuss. Math. Graph Theory 17 (1997), 229-241. https://doi.org/10.7151/DMGT.1050
Frucht R., Harary F. On the Corona of Two Graphs. Aequationes Math. 4 (1970), 322-325. https://doi.org/10.1007/BF01844162
Sharma R., Adhikari B., Mishra A. Structural and Spectral Properties of Corona Graphs. Discrete Appl. Math. 228 (2017), 14-31. https://doi.org/10.1016/j.dam.2017.01.005
Arumugam S., Lee Yi-Chun et al. On Local Antimagic Vertex Coloring for Corona Products of Graphs. Combinatorics (2018). https://arxiv.org/abs/1808.04956
Thiru V.S., Balaji S. Strong Chromatic Indices of Certain Binary Operations on Graphs. Discrete Math. Algorithms Appl. 16 (2024), 2350073. https://doi.org/10.1142/S1793830923500738
Izbicki H. Zulässige Kantenfärbungen von Pseudo-regulären Graphen mit Minimaler Kantenfarbenzahl. Monatsh. Math. 67 (1963), 25-31. https://doi.org/10.1007/BF01300678
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Proceedings of the YSU
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
