On locally irregular decompositions and the 1-2 Conjecture in digraphsArticleAuthors: Olivier Baudon
1; Julien Bensmail
2; Jakub Przybyło
3; Mariusz Woźniak
3
NULL##NULL##0000-0002-1262-7017##NULL
Olivier Baudon;Julien Bensmail;Jakub Przybyło;Mariusz Woźniak
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.
Volume: vol. 20 no. 2
Section: Graph Theory
Published on: October 1, 2018
Accepted on: September 21, 2018
Submitted on: April 30, 2018
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] 1-2 Conjecture, locally irregular decompositions, digraphs
Funding:
Source : OpenAIRE Graph- Graph Theory: Colourings, flows, and decompositions; Funder: European Commission; Code: 320812; Call ID: ERC-2012-ADG_20120216; Projet Financing: ERC-2012-ADG_20120216
- Structures Interdites; Funder: French National Research Agency (ANR); Code: ANR-13-BS02-0007