pith. sign in

arxiv: 2605.18634 · v1 · pith:N6I4RNDInew · submitted 2026-05-18 · 🧮 math.CO · cs.DM

Harmonious Colorings: bounds, heuristics and integer-linear formulations

J\'ulio Ara\'ujo , Manoel Camp\^elo , Beatriz Martins , Marcio C. Santos This is my paper

Pith reviewed 2026-05-20 08:59 UTC · model grok-4.3

classification 🧮 math.CO cs.DM MSC 05C15
keywords harmonious coloringchromatic numberinteger linear programminggraph coloringheuristicsupper boundsvertex identification
0
0 comments X

The pith

Integer linear programs model harmonious colorings by enforcing unique color pairs on every pair of edges.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops exact computational methods and refined bounds for the harmonious chromatic number of graphs. It shows how to relate the numbers for a graph and a version obtained by merging vertices that are far apart, then corrects an earlier proof to tighten an upper bound. The central advance is the first integer-linear programming formulations for the problem together with accompanying heuristics. These are applied to random graphs and to instances from the DIMACS challenge.

Core claim

The authors present integer-linear programming formulations for harmonious coloring that use binary variables to indicate color assignments to vertices and ensure that each unordered pair of distinct colors is used on at most one edge. They also provide heuristics based on these ideas and demonstrate their use on various graph instances, while extending prior comparison techniques and correcting an upper-bound proof.

What carries the argument

Integer-linear programming formulations that assign colors to vertices while enforcing that each unordered pair of colors appears on at most one edge.

If this is right

  • Solving the ILPs to optimality yields the exact harmonious chromatic number for the given graph.
  • The corrected proof supplies a strictly stronger upper bound on the harmonious chromatic number than previously available.
  • The formulations allow direct numerical comparison of the parameter between a graph and the graph obtained by identifying vertices at distance three or more.
  • The heuristics supply feasible colorings quickly on instances too large for exact solution.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Off-the-shelf MIP solvers can now be applied directly to moderate-sized harmonious-coloring instances.
  • The vertex-identification comparison may transfer to other edge-pair-constrained coloring parameters.
  • The same modeling ideas could be adapted to find lower bounds by relaxing the pair-uniqueness constraints.

Load-bearing premise

The integer linear programs accurately represent all valid harmonious colorings without allowing invalid ones or excluding possible solutions.

What would settle it

Running the ILP to optimality on a small graph whose harmonious chromatic number is already known by exhaustive enumeration and obtaining a different number of colors.

Figures

Figures reproduced from arXiv: 2605.18634 by Beatriz Martins, J\'ulio Ara\'ujo, Manoel Camp\^elo, Marcio C. Santos.

Figure 1
Figure 1. Figure 1: Sumary of the computational results for the set of instances [PITH_FULL_IMAGE:figures/full_fig_p017_1.png] view at source ↗
read the original abstract

A proper coloring $c$ of a simple graph $G$ is harmonious if, for every pair of distinct edges $uv,xy\in E(G)$, we have that $\{c(u),c(v)\}\neq \{c(x),c(y)\}$. The harmonious chromatic number of $G$, denoted by $h(G)$, is the least positive integer $k$ such that $G$ has a harmonious coloring with $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$ and $H$, with $H$ being obtained from $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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper extends an idea from Kolay et al. to relate the harmonious chromatic numbers h(G) and h(H) when H is formed from G by identifying vertices at distance at least three. It corrects a proof in that prior work to strengthen one upper bound. The central contribution is the introduction of the first integer-linear programming formulations for harmonious coloring (along with heuristics), together with preliminary computational tests on random graphs and selected DIMACS instances.

Significance. If the ILP models are shown to be correct, the work supplies the first exact mathematical-programming approach to computing or bounding the harmonious chromatic number, a parameter whose exact values remain unknown for many graph families. The bound improvement and vertex-identification comparison also add modest theoretical value.

major comments (1)
  1. [ILP formulations section] ILP formulations section: the models are asserted to enforce that every pair of distinct edges receives a distinct unordered pair of colors, yet the manuscript contains neither a formal correctness argument nor computational verification on small graphs whose harmonious chromatic numbers are known exactly (e.g., complete graphs K_n, odd cycles, or small trees). This verification is load-bearing for the claim that the formulations are the first exact ILPs in the literature.
minor comments (2)
  1. [Introduction / bound section] The description of the proof correction would benefit from an explicit statement of the original error and the precise step that repairs it.
  2. [Computational results] Computational tables should report both the obtained upper bounds and the running times or solver status for each instance to allow direct comparison with existing heuristics.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and for the constructive comment on the ILP formulations. We address the point below and will incorporate the suggested additions in the revised version.

read point-by-point responses

  1. Referee: ILP formulations section: the models are asserted to enforce that every pair of distinct edges receives a distinct unordered pair of colors, yet the manuscript contains neither a formal correctness argument nor computational verification on small graphs whose harmonious chromatic numbers are known exactly (e.g., complete graphs K_n, odd cycles, or small trees). This verification is load-bearing for the claim that the formulations are the first exact ILPs in the literature.

    Authors: We agree that the submitted manuscript would benefit from an explicit formal argument establishing correctness of the ILP models together with direct computational checks on small graphs whose harmonious chromatic numbers are known exactly. In the revision we will add a self-contained proof that the proposed constraints (edge-color-pair uniqueness, proper coloring, and integrality) are necessary and sufficient to enforce the harmonious-coloring condition. We will also include a short computational verification subsection reporting optimal values returned by the models on complete graphs K_n (for which h(K_n) = n), odd cycles C_{2k+1} (for which h(C_{2k+1}) = 2k+1 or 2k+2 depending on parity), and small trees whose harmonious numbers are tabulated in the literature. These additions will directly support the novelty claim. revision: yes

Circularity Check

0 steps flagged

No significant circularity; formulations and bounds rest on external definitions and prior independent work

full rationale

The paper defines harmonious coloring from the standard graph-theoretic condition on distinct unordered color pairs for edges, then presents new ILP models and heuristics directly encoding that condition along with a correction to an upper bound from a 2019 paper by unrelated authors. No equations reduce a claimed prediction or result to a fitted parameter or self-referential definition by construction, no load-bearing self-citation chains appear, and the central contributions (first ILP models, bound fix) retain independent content from the cited source and standard definitions. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on the standard definition of proper coloring and the harmonious condition; no new free parameters or invented entities are introduced beyond the ILP variables themselves.

axioms (2)
  • standard math A proper vertex coloring ensures adjacent vertices receive different colors.
    Invoked in the definition of harmonious coloring.
  • domain assumption Identifying vertices at distance at least three produces a well-defined graph whose harmonious chromatic number relates to the original in a comparable way.
    Basis for the extension of the Kolay et al. comparison technique.

pith-pipeline@v0.9.0 · 5753 in / 1300 out tokens · 53081 ms · 2026-05-20T08:59:34.022853+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    , booktitle =

    Karp, Richard M. , booktitle =. Reducibility Among Combinatorial Problems. , url =

    work page

  2. [2]

    The complexity of harmonious colouring for trees , journal =

    Keith Edwards and Colin McDiarmid , abstract =. The complexity of harmonious colouring for trees , journal =. 1995 , note =. doi:https://doi.org/10.1016/0166-218X(94)00100-R , url =

    work page doi:10.1016/0166-218x(94)00100-r 1995

  3. [3]

    AKCE International Journal of Graphs and Combinatorics , volume=

    Further results on harmonious colorings of digraphs , author=. AKCE International Journal of Graphs and Combinatorics , volume=. 2011 , publisher=

    work page 2011

  4. [4]

    Journal of graph theory , volume=

    An upper bound for the harmonious chromatic number of a graph , author=. Journal of graph theory , volume=. 1987 , publisher=

    work page 1987

  5. [5]

    Hopcroft, J. E. and Krishnamoorthy, M. S. , title =. SIAM Journal on Algebraic Discrete Methods , volume =. 1983 , doi =

    work page 1983

  6. [6]

    Theoretical Computer Science , volume=

    Harmonious coloring: Parameterized algorithms and upper bounds , author=. Theoretical Computer Science , volume=. 2019 , publisher=

    work page 2019

  7. [7]

    Discrete Mathematics , volume=

    The harmonious coloring number of a graph , author=. Discrete Mathematics , volume=. 1991 , publisher=

    work page 1991

  8. [8]

    Matematicheskii sbornik , volume=

    On some properties of linear complexes , author=. Matematicheskii sbornik , volume=. 1949 , publisher=

    work page 1949

  9. [9]

    ON HARMONIOUS COLORINGS OF REGULAR DIGRAPHS1 , author=

    work page

  10. [10]

    Discrete Applied Mathematics , volume=

    Harmonious chromatic number of directed graphs , author=. Discrete Applied Mathematics , volume=. 2013 , publisher=

    work page 2013

  11. [11]

    2013 , school=

    A Study of Harmonious and Complete Colorings of Digraphs , author=. 2013 , school=

    work page 2013

  12. [12]

    Harmonious colorings of digraphs , author=

    work page

  13. [13]

    The harmonious coloring problem is

    Asdre, Katerina and Ioannidou, Kyriaki and Nikolopoulos, Stavros D , journal=. The harmonious coloring problem is. 2007 , publisher=

    work page 2007

  14. [14]

    Information Processing Letters , volume=

    Achromatic number is NP-complete for cographs and interval graphs , author=. Information Processing Letters , volume=. 1989 , publisher=

    work page 1989

  15. [15]

    2019 , address =

    Oliveira, Hismael , title=. 2019 , address =

    work page 2019

  16. [16]

    2015 , note=

    Trick, Michael and Chvatal, Vavsek and Cook, Bill and Johnson, David and McGeoch, Cathy and Tarjan, Bob , title=. 2015 , note=

    work page 2015

  17. [17]

    Journal of graph theory , volume=

    The growth rate of the harmonious chromatic number , author=. Journal of graph theory , volume=. 1989 , publisher=

    work page 1989

  18. [18]

    Govindarajan, Ms.V.Kavitha , year =

    Dr.R. Govindarajan, Ms.V.Kavitha , year =. On A Harmonious Colouring Graphs And Its Applications , volume =. IOSR Journal of Mathematics , doi =

    work page

  19. [19]

    Applied Mathematical Sciences , volume=

    Harmonious coloring of central graphs of certain snake graphs , author=. Applied Mathematical Sciences , volume=. 2015 , publisher=

    work page 2015

  20. [20]

    SIAM Review , volume =

    Gebremedhin, Assefaw Hadish and Manne, Fredrik and Pothen, Alex , title =. SIAM Review , volume =

    work page

  21. [21]

    IEEE Transactions on Circuits and Systems , title=

    M. IEEE Transactions on Circuits and Systems , title=. 1976 , volume=

    work page 1976

  22. [22]

    Gómez and J

    D. Gómez and J. Montero and J. Yáñez and C. Poidomani , keywords =. A graph coloring approach for image segmentation , journal =. 2007 , issn =. doi:https://doi.org/10.1016/j.omega.2005.05.003 , url =

    work page doi:10.1016/j.omega.2005.05.003 2007

  23. [23]

    Information Processing Letters , volume=

    Cliques, holes and the vertex coloring polytope , author=. Information Processing Letters , volume=. 2004 , publisher=

    work page 2004

  24. [24]

    2008 , author =

    On the asymmetric representatives formulation for the vertex coloring problem , journal =. 2008 , author =

    work page 2008

  25. [25]

    , volume=

    The Harmonious Chromatic Number of a Graph , author=. , volume=. 1992 , publisher=

    work page 1992

  26. [26]

    Facets of the Graph Coloring Polytope , volume =

    Coll, Pablo and Marenco, Javier and M. Facets of the Graph Coloring Polytope , volume =. Annals of Operations Research , number =

    work page

  27. [27]

    1996 , publisher=

    Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge , author=. 1996 , publisher=

    work page 1996