1-2-3 Conjecture in digraphs: More results and directions

Julien Bensmail*, Kasper Szabo Lyngsie

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review


Horňak, Przybyło and Woźniak recently proved that, a small class of obvious exceptions apart, every digraph can be 4-arc-weighted so that, for every arc uv⃗, the sum of weights incoming to u is different from the sum of weights outgoing from v. They conjectured a stronger result, namely that the same statement with 3 instead of 4 should also be true. We verify this conjecture in this work. This work takes place in a recent “quest” towards a directed version of the 1–2–3 Conjecture, the variant above being one of the last introduced ones. We take the occasion of this work to establish a summary of all results known in this field, covering known upper bounds, complexity aspects, and choosability. On the way we prove additional results which were missing in the whole picture. We also mention the aspects that remain open.
Original languageEnglish
JournalDiscrete Applied Mathematics
Pages (from-to)124-137
Publication statusPublished - 2020


  • 1–2–3 Conjecture
  • Directed variants
  • Bounds
  • Complexity
  • Choosability

Fingerprint Dive into the research topics of '1-2-3 Conjecture in digraphs: More results and directions'. Together they form a unique fingerprint.

Cite this