Article in volume
Authors:
Title:
Approximate and exact results for the harmonious chromatic number
PDFSource:
Discussiones Mathematicae Graph Theory 44(2) (2024) 737-754
Received: 2021-12-09 , Revised: 2022-07-22 , Accepted: 2022-07-22 , Available online: 2022-09-15 , https://doi.org/10.7151/dmgt.2469
Abstract:
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 $\Omega(\sqrt{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
References:
- 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 - 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 - 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 - 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 - K. Edwards, The harmonious chromatic number of bounded degree trees, Combin. Probab. Comput. 5 (1996) 15–28.
https://doi.org/10.1017/S0963548300001802 - 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 - 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 - O. Frank, F. Harary and M. Plantholt, The line-distinguishing chromatic number of a graph, Ars Combin. 14 (1982) 241–252.
- 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 - 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 - M. I. Huilgol and V. Sriram, On the harmonious coloring of certain class of graphs, J. Comb. Inf. Syst. Sci. 41 (2016) 17–29.
- 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 - 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 - 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 - 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 - A. Mansuri, R. Chandel and V. Gupta, On harmonious coloring of $M(Y_n)$ and $C(Y_n)$, World Appl. Program. 2 (2012) 150–152.
- B. McKay and G. Royle, Constructing the cubic graphs on up to $20$ vertices, Ars Combin. 21-A (1986) 129–140.
- 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 - 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 - U. Muthumari and M. Umamamheswari, Harmonious coloring of central graph of some types of graphs, Int. J. Math. Archive 7(8) (2016) 95–103.
- R.W. Pratt, The complete catalog of $3$-regular, diameter-$3$ planar graphs, (1996).
- 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.
- 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.
- 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 - 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 - 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 - P. Zhang, A Kaleidoscopic View of Graph Colorings, in: SpringerBriefs Math. (Springer Cham, 2016).
https://doi.org/10.1007/978-3-319-30518-9
Close