Baudon , Olivier and Bensmail , Julien and Przybyło , Jakub and Woźniak , Mariusz - On locally irregular decompositions and the 1-2 Conjecture in digraphs

dmtcs:4859 - Discrete Mathematics & Theoretical Computer Science, October 1, 2018, vol. 20 no. 2
On locally irregular decompositions and the 1-2 Conjecture in digraphs

Authors: Baudon , Olivier and Bensmail , Julien and Przybyło , Jakub and Woźniak , Mariusz

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.


Source : oai:HAL:hal-01374427v5
Volume: vol. 20 no. 2
Section: Graph Theory
Published on: October 1, 2018
Submitted on: April 30, 2018
Keywords: 1-2 Conjecture,locally irregular decompositions,digraphs, [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Consultation statistics

This page has been seen 31 times.
This article's PDF has been downloaded 9 times.