Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. On locally irregular ...
Article

On locally irregular decompositions and the 1-2 Conjecture in digraphs

Olivier Baudon (1), Julien Bensmail (2), Jakub Przybyło ORCID (3), Mariusz Woźniak (3)
(1) Laboratoire Bordelais de Recherche en Informatique
(2) Combinatorics, Optimization and Algorithms for Telecommunications
(3) AGH University of Science and Technology [Krakow, PL]
Download article
Open on HAL
Submitted on
April 30, 2018
Accepted on
September 21, 2018
Published on
October 1, 2018
Last modified on
March 31, 2025
Volume 20
vol. 20:2
Graph Theory
DOI
10.23638/DMTCS-20-2-7
License
https://about.hal.science/hal-authorisation-v1
Graph Theory: Colourings, flows, and decompositions
Indicators
1568
Views
861
Downloads

On locally irregular decompositions and the 1-2 Conjecture in digraphs

Olivier Baudon (1), Julien Bensmail (2), Jakub Przybyło ORCID (3), Mariusz Woźniak (3)
(1) Laboratoire Bordelais de Recherche en Informatique
(2) Combinatorics, Optimization and Algorithms for Telecommunications
(3) AGH University of Science and Technology [Krakow, PL]
Abstract
The 1-2 Conjecture raised by Przybylo and Wozniak in 2010 asserts that every undirected graph admits a 2-total-weighting such that the sums of weights "incident" to the vertices yield a proper vertex-colouring. Following several recent works bringing related problems and notions (such as the well-known 1-2-3 Conjecture, and the notion of locally irregular decompositions) to digraphs, we here introduce and study several variants of the 1-2 Conjecture for digraphs. For every such variant, we raise conjectures concerning the number of weights necessary to obtain a desired total-weighting in any digraph. We verify some of these conjectures, while we obtain close results towards the ones that are still open.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • 1-2 Conjecture
  • locally irregular decompositions
  • digraphs
Cited by

Source: OpenCitations

  • Irregularity Notions for Digraphs

    Authors : Julien Bensmail ORCID, Thomas Filasto, Hervé Hocquard ORCID, Clara Marcille

    Journal reference : Volume 41, 2025, pp.

    DOI : 10.1007/s00373-025-02927-4
Preview
Loading PDF preview...