Harmonious Colorings: bounds, heuristics and integer-linear formulations

J. Araújo, M. Campêlo, B. Martins, M. C. Santos · 2026

Read Harmonious Colorings: bounds, heuristics and integer-linear formulations by J. Araújo, M. Campêlo, B. Martins, M. C. Santos (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-18634.txt.

Introduction

Júlio Araújo and three co-authors extend, in a 2026 study, work on harmonious colorings of graphs. In such a coloring, every pair of edges must carry a different color pair. They compare the harmonious chromatic numbers of two graphs when one comes from the other by merging vertices at distance at least three. A fix to an earlier proof tightens one known upper bound. They also give the first integer-linear programming formulations for the problem, plus heuristics, and test them on random cases and DIMACS Challenge instances.

Catalog record

CREATORJ. Araújo, M. Campêlo, B. Martins, M. C. Santos
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50198
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.18634

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Harmonious Colorings: bounds, heuristics and integer-linear formulations Thanks: This work was supported by CNPq 312417/2022-5, 404479/2023-5, 442977/2023-9, 308939/2025-5, 444528/2024-5, 421005/2025-4 and by Projet ANR GODASse, Projet-ANR-24-CE48-4377. J. Araújo, M. Campêlo, B. Martins, M. C. Santos Abstract A proper coloring c c of a simple graph G G is harmonious if, for every pair of distinct edges u ​ v , x ​ y ∈ E ⁡ ( G ) uv,xy\in E(G) , we have that { c ⁡ ( u ) , c ⁡ ( v ) } ≠ { c ⁡ ( x ) , c ⁡ ( y ) } \{c(u),c(v)\}\neq\{c(x),c(y)\} . The harmonious chromatic number of G G , denoted by h ⁡ ( G ) \h(G) , is the least positive integer k k such that G G has a harmonious coloring with k k colors. In this work, we extend an idea presented in [Kolay, et al. Harmonious coloring: Parameterized algorithms and upper bounds. Theor. Comp. Sci. 772 (2019), 132–142] to compare the harmonious chromatic numbers of two graphs G G and H H , with H H being obtained from G G by identifying vertices at distance at least three. Furthermore, by fixing a proof presented in the same work, we manage to improve one of its upper bounds. We also introduce and study the first, to the best of our knowledge, integer-linear programming formulations for this problem in the literature, along with some heuristics. We provide some preliminary tests on random instances and instances from the second DIMACS Implementation Challenge . 1 Introduction Given a simple graph G=(V,E) , a k -coloring of G is a function c:V(G)\to\{1,\ldots,k\} . A k -coloring c is proper if c(u)\neq c(v) for every uv\in E(G) . The chromatic number of G , denoted by \chi(G) , is the minimum positive integer k such that G admits a proper k -coloring. It is well-known that computing \chi(G) is an {\mathsf{NP}} -hard problem [ 13 ] . A k -coloring c (not necessarily proper) is line-distinguishing if, for any pair of distinct edges uv,xy\in E(G) , we have that \{c(u),c(v)\}\neq\{c(x),c(y)\} . The line-distinguishing chromatic number , denoted by \lambda(G) , is the least positive integer k for which G admits a line-distinguishing k -coloring [ 11 ] . A harmonious k -coloring is a proper line-distinguishing k -coloring. The harmonious chromatic number of G , denoted by \h(G) , is the minimum positive integer k such that G has a harmonious k -coloring [ 16 ] . It is worth mentioning that, in their seminal paper, Hopcroft and Krishnamoorthy [ 11 ] used the term Harmonious Coloring to simply mean line-distinguishing coloring; however, since the work of Lee and Mitchem [ 16 ] , the term is dedicated to the version of the problem that requires the coloring to be proper. The distance between two vertices is the length of a shortest path between them (it is +\infty if no such a path exists), and the diameter of a graph is the maximum distance between any two vertices. A harmonious coloring must assign different colors to vertices at distance 1 (since it is proper) or 2 (since it is line-distinguishing). So, complete graphs are not the only n -vertex graphs having a harmonious chromatic number equal to n . Any graph with n vertices and a diameter of at most two must receive n colors in a harmonious coloring [ 17 ] . Graph colorings have been used to model many different types of problems, from computing derivatives [ 9 ] to testing printed circuits [ 8 ] and performing image segmentation [ 10 ] . However, harmonious graph coloring has been studied mainly from a theoretical point of view for several years [ 6 ] . In the scarce literature on direct applications of harmonious coloring, we can cite its use in modeling a radio navigation system [ 19 ] . In this work, we present some results on structural graph theory related to harmonious coloring, alongside integer programming models and computational experiments for determining the harmonious chromatic number of a given graph. Our contributions and related results. In the next two sections, we study upper bounds for \h(G) . Section 2 considers d -degenerate graphs. We say that a graph G is d-degenerate if, for any subgraph H\subseteq G , the minimum degree \delta(H) of H is at most d . The Harmonious Coloring of d -degenerate graphs has been related to vertex cover [ 14 ] . Recall that S\subseteq V(G) is a vertex cover of G if, for any edge uv\in E(G) , we have u\in S or v\in S . Let \vc(G) denote the cardinality of a minimum vertex cover S\subseteq V(G) of a graph G . In [ 14 ] , the authors claim that if G is d -degenerate, then \h(G)\leq\vc(G)+d(\Delta(G)-1)+\Delta(G)(d-1) , where \Delta(G) is the maximum degree of G . In Section 2 , we argue that their proof is incorrect and show a counter-example for d=1 . Besides, we prove that actually \h(G)\leq\vc(G)+d(\Delta(G)-1)+1 , thus providing a tighter bound for d\geq 2 . Section 3 considers arbitrary graphs. Using identifications on vertices at distance at least three, we derive a sufficient condition for a graph to have a harmonious chromatic number at most k . We remark that part of our argument is similar to the one used in [ 14 ] to identify color classes in a harmonious coloring as part of a fixed-parameter tractable algorithm to compute \h(G) , parameterized by \vc(G) . Computing the harmonious chromatic number of a graph is a hard task. Given a graph G and a positive integer k , determining whether \h(G)\leq k is {\mathsf{NP}} -complete, even if G is a split graph [ 1 ] , or an interval graph [ 1 , 2 ] , or a tree of radius three, or a forest consisting of three trees of radius two [ 7 ] . To address this computational hardness, Section 4 is devoted to presenting Integer Linear Programming formulations, Section 5 proposes two heuristics for the problem, and Section 6 presents computational results for the formulations and heuristics on random instances. We introduce three integer linear programming models, two of them based on the representatives formulation presented in [ 4 ] . To the best of our knowledge, this is the first work to present a mathematical programming approach for harmonious coloring. By the way, the first integer-linear programming formulations to compute the line-distinguishing chromatic number were proposed only recently [ 18 ] . Of course, these formulations do not impose the constraint that the coloring must be proper. We emphasize that we do not only add this constraint to the formulation presented in [ 18 ] . We present a new set of \mathcal{O}(n^{3}) constraints to ensure a line-distinguishing coloring, which improves the \mathcal{O}(n^{4}) constraints proposed in [ 18 ] , where n stands for the number of vertices of the input graph. We present computational experiments to test our formulations and heuristics on random instances as well as on instances from the second DIMACS Implementation Challenge [ 20 ] . 2 Bound on the vertex cover

Read the complete text