On the Edge-Difference and Edge-Sum Chromatic Sum of the Simple Graphs

Document Type : Research Paper

Authors

School of Mathematical Science, Shahrood University of Technology, Shahrood, Iran.

Abstract

‎For a coloring $c$ of a graph $G$‎, ‎the edge-difference coloring sum and edge-sum coloring sum with respect to the coloring $c$ are respectively‎ ‎$\sum_c D(G)=\sum |c(a)-c(b)|$ and $\sum_s S(G)=\sum (c(a)+c(b))$‎, ‎where the summations are taken over all edges $ab\in E(G)$‎. ‎The edge-difference chromatic sum‎, ‎denoted by $\sum D(G)$‎, ‎and the edge-sum chromatic sum‎, ‎denoted by $\sum S(G)$‎, ‎are respectively the minimum possible values‎ ‎of $\sum_c D(G)$ and $\sum_c S(G)$‎, ‎where the minimums are taken over all proper coloring of $c$‎. ‎In this work‎, ‎we study the edge-difference chromatic sum and the edge-sum chromatic sum of graphs‎. ‎In this regard‎, ‎we present some necessary conditions for the existence of homomorphism between two graphs‎. ‎Moreover‎, ‎some upper and lower bounds for these parameters in terms of the fractional chromatic number are introduced‎ ‎as well‎.

Keywords


[1] M. Alishahi and A. Taherkhani, A Note on Chromatic Sum, To appear, Ars Combinatoria. Available at
arXiv:0802.1936.
[2] E. Kubicka, The chromatic sum of a graph, Western Michigan University, 1989, Michigan.
[3] K. J. Supowit, Finding a Maximum Planar Subset of a Set of Nets in a Channel, Trans. Comp.-Aided Des.
Integ. Cir. Sys., 6 (1) (2006) 93-94.
[4] M.R. Garey, and D.S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness,
W. H. Freeman & Co., New York, NY, USA, 1990.
[5] K. E. Stecke, Design, planning, scheduling, and control problems of flexible manufacturing systems, Annals
of Operations Research, 3 (1) (1985), 1-12.
[6] C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-
Hall, Inc., Upper Saddle River, NJ, USA, 1982.
[7] E. K. Burke and B. McCollum and A. Meisels and S. Petrovic and R. Qu, A graph-based hyper heuristic
for educational timetabling problems, European Journal of Operational Research, 176 (1) (2007), 177 - 192.
[8] D.H. Smith and S. Hurley and S.U. Thiel, Improving heuristics for the frequency assignment problem,
European Journal of Operational Research, 107, (1) (1998)76-86.
[9] D. de Werra and Ch. Eisenbeis and S. Lelait and B. Marmol, On a graph theoretical model for cyclic register
allocation, Discrete Applied Mathematics, 93 (2-3) (1999) 191-203.
[10] M. Gamache and A. Hertz and J. O. Ouellet, A Graph Coloring Model for a Feasibility Problem in Monthly
Crew Scheduling with Preferential Bidding, Comput. Oper. Res., 34 (8) (2007) 2384-2395.
[11] C. A. Glass, Bag rationalisation for a food manufacturer, Journal of the Operational Research Society, 53
(5) (2002) 544-551.
[12] P. Erdos and E. Kubicka and A. J. Schwenk, Graphs that require many colors to achieve their chromatic
sum, In Proceedings of the Twentieth South-eastern Conference on Combinatorics Graph Theory and
Computing, 71 (1990) 17-28.
[13] Yu. Li, C. Lucet, A. Moukrim, K. Sghiouer, Greedy Algorithms for the Minimum Sum Coloring Problem,
(2007) Sousse, Tunisia.
[14] H. Hajiabolhassan and M.L. Mehrabadi and R. Tusserkani, Minimal coloring and strength of graphs, Dis-
crete Mathematics, 215 (1) (2000) 265 - 270.
[15] H. Hajiabolhassan and M. L. Mehrabadi and R. Tusserkani, Tabular Graphs and Chromatic Sum, Discrete
Mathematics, 304 (1-3) (2005) 11–22.
[16] L. G. Kroon, A. Sen, H. Deng and A. Roy, The Optimal Cost Chromatic Partition problem for trees and
interval graphs, Graph-Theoretic Concepts in Computer Science: 22nd International Workshop (1997)
279-292.
[17] T. Jiang and D. B. West, Coloring of Trees with Minimum Sum of Colors, J. Graph Theory, 32 (4) (1999)
354–358.
[18] E. Kubicka A. J. and Schwenk, An Introduction to Chromatic Sums, Proceedings of the 17th Conference
on ACM Annual Computer Science Conference, (1989) 39-45.
[19] , C. Thomassen and P. Erdos and Y. Alavi and P. J. Malde and A. J. Schwenk, Tight bounds on the
chromatic sum of a connected graph, Journal of Graph Theory, 13 (3) (1989) 353-357.
[20] U. Benlic and J. K. Hao, A Study of Breakout Local Search for the Minimum Sum Coloring Problem,
Simulated Evolution and Learning: 9th International Conference, (2012) 128-137.
[21] M. Malafiejski, Sum coloring of graphs, Contemporary Mathematics: Graph Colorings, (2004) 55-65.
[22] E..R. Scheinerman and D.H. Ullman, Fractional graph theory: A rational approach to the theory of graphs,
John Wiley & Sons Inc., New York, 1997.
[23] P. Hell and J. Nesatril, Graphs and homomorphisms, Oxford University Press, 2004.