An Improved Bound for Equitable Proper Labellings - Université Côte d'Azur Access content directly
Conference Papers Year : 2024

An Improved Bound for Equitable Proper Labellings


For every graph $G$ with size $m$ and no connected component isomorphic to $K_2$, we prove that, for $L=(1,1,2,2,\dots,\lfloor m/2 \rfloor+2,\lfloor m/2 \rfloor+2)$, we can assign labels of $L$ to the edges of $G$ in an injective way so that no two adjacent vertices of $G$ are incident to the same sum of labels. This implies that every such graph with size $m$ can be labelled in an equitable and proper way with labels from $\{1,\dots,\lfloor m/2 \rfloor+2\}$, which improves on a result proved by Haslegrave, and Szabo Lyngsie and Zhong, implying this can be achieved with labels from $\{1,\dots,m\}$.
Fichier principal
Vignette du fichier
iwoca_revised.pdf (489.1 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-04564833 , version 1 (30-04-2024)


  • HAL Id : hal-04564833 , version 1


Julien Bensmail, Clara Marcille. An Improved Bound for Equitable Proper Labellings. IWOCA 2024 - 35th International Workshop on Combinatorial Algorithms, Jul 2024, Ischia, Italy. ⟨hal-04564833⟩
0 View
0 Download


Gmail Facebook X LinkedIn More