Geodesic
Approximate and exact results for the harmonious chromatic number
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 737-754

Voir la notice de l'article provenant de la source Library of Science

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},
     publisher = {mathdoc},
     volume = {44},
     number = {2},
     year = {2024},
     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
PB  - mathdoc
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
%I mathdoc
%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/