Skip to main content
Article
The 1 , 2 , 3-Conjecture And 1 , 2-Conjecture For Sparse Graphs
Discussiones Mathematicae Graph Theory (2014)
  • Daniel W. Cranston, Virginia Commonwealth University
  • Sogol Jahanbekam, University of Illinois at Urbana–Champaign
  • Douglas B. West, University of Illinois at Urbana–Champaign
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.
Keywords
  • reducible configuration,
  • discharging method
Publication Date
January 1, 2014
DOI
10.7151/dmgt.1768
Publisher Statement
This article was published in Discussiones Mathematicae Graph Theory, volume 34, issue 4, and can also be found online at this link.

This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivatives licence.
Citation Information
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 Vol. 34 Iss. 4 (2014) p. 769 - 799 ISSN: 2083-5892
Available at: http://works.bepress.com/sogol-jahanbekam/9/
Creative Commons license
Creative Commons License
This work is licensed under a Creative Commons CC_BY-NC-ND International License.