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/

[1] L. Addario-Berry, K. Dalal, C. McDiarmid, B.A. Reed and A. Thomason, Vertex-colouring edge-weightings, Combinatorica 27 (2007) 1-12. doi:10.1007/s00493-007-0041-6

[2] L. Addario-Berry, K. Dalal and B.A. Reed, Degree constrained subgraphs, Discrete Appl. Math. 156 (2008) 1168-1174. doi:10.1016/j.dam.2007.05.059

[3] N. Alon, Combinatorial Nullstellensatz, Combin. Probab. Comput. 8 (1999) 7-29. doi:10.1017/S0963548398003411

[4] T. Bartnicki, J. Grytczuk and S. Niwczyk, Weight choosability of graphs, J. Graph Theory 60 (2009) 242-256. doi:10.1002/jgt.20354

[5] M. Kalkowski, A note on the 1, 2-conjecture, submitted (also in Ph.D. Thesis, 2009).

[6] M. Kalkowski, M. Karoński and F. Pfender, Vertex-coloring edge-weightings: towards the 1-2-3-conjecture, J. Combin. Theory (B) 100 (2010) 347-349. doi:10.1016/j.jctb.2009.06.002

[7] M. Karónski, T. Luczak and A. Thomason, Edge weights and vertex colours, J. Combin. Theory (B) 91 (2004) 151-157. doi:10.1016/j.jctb.2003.12.001

[8] J. Przybyło and M. Woźniak, On a 1, 2 conjecture, Discrete Math. Theoret. Comput. Sci. 12 (2010) 101-108.

[9] B. Seamone, The 1-2-3 conjecture and related problems: a survey, submitted (http://arxiv.org/abs/1211.5122).

[10] T. Wang and Q. Yu, On vertex-coloring 13-edge-weighting, Front. Math. China 3 (2008) 581-587. doi:10.1007/s11464-008-0041-x

[11] T.-L. Wong, X. Zhu and D. Yang, List total weighting of graphs, in: G.O.H. Katona, A. Schrijver, T. Szőnyi and G. Sági, Eds., Fete of Combinatorics and Computer Science, Bolyai Soc. Math. Stud., vol. 20 (Springer, Berlin, Heidelberg, 2010) 337-353. doi:10.1007/978-3-642-13580-4 13

[12] T.-L. Wong and X. Zhu, Total weight choosability of graphs, J. Graph Theory 66 (2011) 198-212. doi:10.1002/jgt.20500

[13] T.-L. Wong and X. Zhu, Every graph is (2, 3)-choosable, submitted.