Geodesic
An Oriented Version of the 1-2-3 Conjecture
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 1, pp. 141-156

Voir la notice de l'article provenant de la source Library of Science

The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph G with no isolated edge can be assigned weights from 1, 2, 3 so that the sum of incident weights at each vertex yields a proper vertex-colouring of G. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph G can be assigned weights from 1, 2, 3 so that every two adjacent vertices of G receive distinct sums of outgoing weights. This result is tight in the sense that some oriented graphs do not admit such an assignment using the weights from 1, 2 only. We finally prove that deciding whether two weights are sufficient for a given oriented graph is an 𝖭𝖯-complete problem. These results also hold for product or list versions of this problem.
Keywords: oriented graph, neighbour-sum-distinguishing arc-weighting, complexity, 1-2-3 Conjecture 
@article{DMGT_2015_35_1_a11,
     author = {Baudon, Olivier and Bensmail, Julien and Sopena, \'Eric},
     title = {An {Oriented} {Version} of the 1-2-3 {Conjecture}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {141--156},
     publisher = {mathdoc},
     volume = {35},
     number = {1},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_1_a11/}
}
TY  - JOUR
AU  - Baudon, Olivier
AU  - Bensmail, Julien
AU  - Sopena, Éric
TI  - An Oriented Version of the 1-2-3 Conjecture
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 141
EP  - 156
VL  - 35
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_1_a11/
LA  - en
ID  - DMGT_2015_35_1_a11
ER  - 
%0 Journal Article
%A Baudon, Olivier
%A Bensmail, Julien
%A Sopena, Éric
%T An Oriented Version of the 1-2-3 Conjecture
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 141-156
%V 35
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_1_a11/
%G en
%F DMGT_2015_35_1_a11
Baudon, Olivier; Bensmail, Julien; Sopena, Éric. An Oriented Version of the 1-2-3 Conjecture. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 1, pp. 141-156. http://geodesic.mathdoc.fr/item/DMGT_2015_35_1_a11/