# The 1 , 2 , 3-Conjecture And 1 , 2-Conjecture For Sparse Graphs

Daniel W. Cranston; Sogol Jahanbekam; Douglas B. West

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 4, page 769-799
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topDaniel W. Cranston, Sogol Jahanbekam, and Douglas B. West. "The 1 , 2 , 3-Conjecture And 1 , 2-Conjecture For Sparse Graphs." Discussiones Mathematicae Graph Theory 34.4 (2014): 769-799. <http://eudml.org/doc/269827>.

@article{DanielW2014,

abstract = {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.},

author = {Daniel W. Cranston, Sogol Jahanbekam, Douglas B. West},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {1; 2; 3-Conjecture; 1; 2-Conjecture; reducible configuration; discharging method.; -conjecture; -conjecture; discharging method},

language = {eng},

number = {4},

pages = {769-799},

title = {The 1 , 2 , 3-Conjecture And 1 , 2-Conjecture For Sparse Graphs},

url = {http://eudml.org/doc/269827},

volume = {34},

year = {2014},

}

TY - JOUR

AU - Daniel W. Cranston

AU - Sogol Jahanbekam

AU - Douglas B. West

TI - The 1 , 2 , 3-Conjecture And 1 , 2-Conjecture For Sparse Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 4

SP - 769

EP - 799

AB - 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.

LA - eng

KW - 1; 2; 3-Conjecture; 1; 2-Conjecture; reducible configuration; discharging method.; -conjecture; -conjecture; discharging method

UR - http://eudml.org/doc/269827

ER -

## References

top- [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 Zbl1147.05055
- [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 Zbl1210.05138
- [5] M. Kalkowski, A note on the 1, 2-conjecture, submitted (also in Ph.D. Thesis, 2009).
- [6] M. Kalkowski, M. Karónski 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 Zbl1209.05087
- [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 Zbl1042.05045
- [8] J. Przyby lo and M. Wózniak, 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). Zbl1302.05059
- [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 Zbl1191.05048
- [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 Zbl1237.05095
- [12] T.-L. Wong and X. Zhu, Total weight choosability of graphs, J. Graph Theory 66 (2011) 198-212. doi:10.1002/jgt.20500 Zbl1228.05161
- [13] T.-L. Wong and X. Zhu, Every graph is (2, 3)-choosable, submitted.