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

Abstract

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

How to cite

top

Daniel 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. [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. [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. [3] N. Alon, Combinatorial Nullstellensatz , Combin. Probab. Comput. 8 (1999) 7-29. doi:10.1017/S0963548398003411 
  4. [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. [5] M. Kalkowski, A note on the 1, 2-conjecture, submitted (also in Ph.D. Thesis, 2009). 
  6. [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. [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. [8] J. Przyby lo and M. Wózniak, On a 1, 2 conjecture, Discrete Math. Theoret. Comput. Sci. 12 (2010) 101-108. 
  9. [9] B. Seamone, The 1-2-3 conjecture and related problems: a survey, submitted (http://arxiv.org/abs/1211.5122). Zbl1302.05059
  10. [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. [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. [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. [13] T.-L. Wong and X. Zhu, Every graph is (2, 3)-choosable, submitted. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.