Geodesic
Approximate and exact results for the harmonious chromatic number
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 737-754 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Graph coloring is a fundamental topic in graph theory that requires an assignment of labels (or colors) to vertices or edges subject to various constraints. We focus on the harmonious coloring of a graph, which is a proper vertex coloring such that for every two distinct colors i, j at most one pair of adjacent vertices are colored with i and j. This type of coloring is edge-distinguishing and has potential applications in transportation networks, computer networks, airway network systems. The results presented in this paper fall into two categories: in the first part of the paper we are concerned with the computational aspects of finding a minimum harmonious coloring and in the second part we determine the exact value of the harmonious chromatic number for some particular graphs and classes of graphs. More precisely, in the first part we show that finding a minimum harmonious coloring for arbitrary graphs is APX-hard and that the natural greedy algorithm is a Ω(√(n))-approximation. In the second part, we determine the exact value of the harmonious chromatic number for all 3-regular planar graphs of diameter 3 and some cycle-related graphs.
Keywords: undirected graph, vertex coloring, harmonious coloring, harmonious chromatic number, regular graph, APX-hard 
@article{DMGT_2024_44_2_a16,
     author = {Marinescu-Ghemeci, Ruxandra and Obreja, Camelia and Popa, Alexandru},
     title = {Approximate and exact results for the harmonious chromatic number},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {737--754},
     year = {2024},
     volume = {44},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a16/}
}
TY  - JOUR
AU  - Marinescu-Ghemeci, Ruxandra
AU  - Obreja, Camelia
AU  - Popa, Alexandru
TI  - Approximate and exact results for the harmonious chromatic number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 737
EP  - 754
VL  - 44
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a16/
LA  - en
ID  - DMGT_2024_44_2_a16
ER  - 
%0 Journal Article
%A Marinescu-Ghemeci, Ruxandra
%A Obreja, Camelia
%A Popa, Alexandru
%T Approximate and exact results for the harmonious chromatic number
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 737-754
%V 44
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a16/
%G en
%F DMGT_2024_44_2_a16
Marinescu-Ghemeci, Ruxandra; Obreja, Camelia; Popa, Alexandru. Approximate and exact results for the harmonious chromatic number. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 737-754. http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a16/

[1] K. Asdre and S.D. Nikolopoulos, NP-completeness results for some problems on subclasses of bipartite and chordal graphs, Theoret. Comput. Sci. 381 (2007) 248–259. https://doi.org/10.1016/j.tcs.2007.05.012

[2] K. Asdre, K. Ioannidou and S.D. Nikolopoulos, The harmonious coloring problem is NP-complete for interval and permutation graphs, Discrete Appl. Math. 155 (2007) 2377–2382. https://doi.org/10.1016/j.dam.2007.07.005

[3] H.L. Bodlaender, Achromatic number is NP-complete for cographs and interval graphs, Inform. Process. Lett. 31 (1989) 135–138. https://doi.org/10.1016/0020-0190(89)90221-4

[4] I. Dinur and S. Safra, On the hardness of approximating minimum vertex cover, Ann. of Math. (2) 162 (2005) 439–485. https://doi.org/10.4007/annals.2005.162.439

[5] K. Edwards, The harmonious chromatic number of bounded degree trees, Combin. Probab. Comput. 5 (1996) 15–28. https://doi.org/10.1017/S0963548300001802

[6] K. Edwards, The harmonious chromatic number and the achromatic number, in: Surveys in Combinatorics, R.A. Bailey (Ed(s)), (London Math. Soc. Lecture Note Ser. 241, Cambridge University Press 1997) 13–48. https://doi.org/10.1017/CBO9780511662119.003

[7] K. Edwards and C. McDiarmid, The complexity of harmonious colouring for trees, Discrete Appl. Math. 57 (1995) 133–144. https://doi.org/10.1016/0166-218X(94)00100-R

[8] O. Frank, F. Harary and M. Plantholt, The line-distinguishing chromatic number of a graph, Ars Combin. 14 (1982) 241–252.

[9] R.L. Graham and N.J.A. Sloane, On additive bases and harmonious graphs, SIAM J. Alg. Disc. Meth. 1 (1980) 382–404. https://doi.org/10.1137/0601045

[10] J.E. Hopcroft and M.S. Krishnamoorthy, On the harmonious coloring of graphs, SIAM J. Alg. Disc. Meth. 4 (1983) 306–311. https://doi.org/10.1137/0604032

[11] M. I. Huilgol and V. Sriram, On the harmonious coloring of certain class of graphs, J. Comb. Inf. Syst. Sci. 41 (2016) 17–29.

[12] K. Ioannidou and S. Nikolopoulos, Harmonious coloring on subclasses of colinear graphs, in: WALCOM: Algorithms and Computation. WALCOM 2010, Lecture Notes in Comput. Sci. 5942, (Springer-Verlag, Berlin, Heidelberg 2010) 136–148. https://doi.org/10.1007/978-3-642-11440-3_13

[13] S. Khot and O. Regev, Vertex cover might be hard to approximate to within 2-\varepsilon, J. Comput. System Sci. 74 (2008) 335–349. https://doi.org/10.1016/j.jcss.2007.06.019

[14] S. Kolay, R. Pandurangan, F. Panolan, V. Raman and P. Tale, Harmonious coloring: Parameterized algorithms and upper bounds, Theoret. Comput. Sci. 772 (2019) 132–142. https://doi.org/10.1016/j.tcs.2018.12.011

[15] Z. Lu, On an upper bound for the harmonious chromatic number of a graph, J. Graph Theory 15 (1991) 345–347. https://doi.org/10.1002/jgt.3190150402

[16] A. Mansuri, R. Chandel and V. Gupta, On harmonious coloring of M(Yn) and C(Yn), World Appl. Program. 2 (2012) 150–152.

[17] B. McKay and G. Royle, Constructing the cubic graphs on up to 20 vertices, Ars Combin. 21-A (1986) 129–140.

[18] Z. Miller and D. Pritikin, The harmonious coloring number of a graph, Discrete Math. 93 (1991) 211–228. https://doi.org/10.1016/0012-365X(91)90257-3

[19] J. Mitchem, On the harmonious chromatic number of a graph, Discrete Math. 74 (1989) 151–157. https://doi.org/10.1016/0012-365X(89)90207-0

[20] U. Muthumari and M. Umamamheswari, Harmonious coloring of central graph of some types of graphs, Int. J. Math. Archive 7(8) (2016) 95–103.

[21] R.W. Pratt, The complete catalog of 3-regular, diameter-3 planar graphs, (1996).

[22] K. Rajam and M.H.M. Pauline, On harmonious colouring of line graph of star graph families, Int. J. Stat. Math. 7 (2013) 33–36.

[23] M.S. Franklin Thamil Selvi and A. Azhaguvel, A study on harmonious coloring of central graph of Jahangir graph, Int. J. Pure Appl. Math. 118 (2018) 413–420.

[24] M.S. Franklin Thamil Selvi, Harmonious coloring of central graphs of certain snake graphs, Appl. Math. Sci. 9 (2015) 569–578. https://doi.org/10.12988/ams.2015.4121012

[25] A. Takaoka, S. Okuma, S. Tayu and S. Ueno, A note on harmonious coloring of caterpillars, IEICE Trans. Inf. Syst. E98.D (2015) 2199–2206. https://doi.org/10.1587/transinf.2015EDP7113

[26] V. Vernold, M. Venkatachalam and K. Kaliraj, Harmonious coloring on double star graph families, Tamkang J. Math. 43 (2012) 153–158. https://doi.org/10.5556/j.tkjm.43.2012.153-158

[27] P. Zhang, A Kaleidoscopic View of Graph Colorings, in: SpringerBriefs Math. (Springer Cham, 2016). https://doi.org/10.1007/978-3-319-30518-9