Geodesic
The 1,2,3-Conjecture and 1,2-Conjecture for sparse graphs
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 4, pp. 769-799

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

The 1, 2, 3-Conjecture states that the edges of a graph without isolated edges can be labeled from 1, 2, 3 so that the sums of labels at adjacent vertices are distinct. The 1, 2-Conjecture states that if vertices also receive labels and the vertex label is added to the sum of its incident edge labels, then adjacent vertices can be distinguished using only 1, 2. We show that various configurations cannot occur in minimal counterexamples to these conjectures. Discharging then confirms the conjectures for graphs with maximum average degree less than 8/3. The conjectures are already confirmed for larger families, but the structure theorems and reducibility results are of independent interest.
Keywords: reducible configuration, discharging method, 1, 2, 3-Conjecture, 1, 2-Conjecture 
@article{DMGT_2014_34_4_a8,
     author = {Cranston, Daniel W. and Jahanbekam, Sogol and West, Douglas B.},
     title = {The {1,2,3-Conjecture} and {1,2-Conjecture} for sparse graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {769--799},
     publisher = {mathdoc},
     volume = {34},
     number = {4},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_4_a8/}
}
TY  - JOUR
AU  - Cranston, Daniel W.
AU  - Jahanbekam, Sogol
AU  - West, Douglas B.
TI  - The 1,2,3-Conjecture and 1,2-Conjecture for sparse graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 769
EP  - 799
VL  - 34
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_4_a8/
LA  - en
ID  - DMGT_2014_34_4_a8
ER  - 
%0 Journal Article
%A Cranston, Daniel W.
%A Jahanbekam, Sogol
%A West, Douglas B.
%T The 1,2,3-Conjecture and 1,2-Conjecture for sparse graphs
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 769-799
%V 34
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_4_a8/
%G en
%F DMGT_2014_34_4_a8
Cranston, Daniel W.; Jahanbekam, Sogol; West, Douglas B. The 1,2,3-Conjecture and 1,2-Conjecture for sparse graphs. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 4, pp. 769-799. http://geodesic.mathdoc.fr/item/DMGT_2014_34_4_a8/