Harmonious Colorings: bounds, heuristics and integer-linear formulations
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911694962294784 |
|---|---|
| author | Araújo, Júlio Campêlo, Manoel Martins, Beatriz Santos, Marcio C. |
| author_facet | Araújo, Júlio Campêlo, Manoel Martins, Beatriz Santos, Marcio C. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_18634 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Harmonious Colorings: bounds, heuristics and integer-linear formulations Araújo, Júlio Campêlo, Manoel Martins, Beatriz Santos, Marcio C. Combinatorics Discrete Mathematics 68R10 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. |
| title | Harmonious Colorings: bounds, heuristics and integer-linear formulations |
| topic | Combinatorics Discrete Mathematics 68R10 |
| url | https://arxiv.org/abs/2605.18634 |