Document Type : Research Paper

**Authors**

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

10.29252/asta.4.1.33

**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.

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**

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.

Winter and Spring 2017

Pages 33-42