- Tytuł:
- The 1,2,3-Conjecture and 1,2-Conjecture for sparse graphs
- Autorzy:
-
Cranston, Daniel W.
Jahanbekam, Sogol
West, Douglas B. - Powiązania:
- https://bibliotekanauki.pl/articles/30148718.pdf
- Data publikacji:
- 2014-11-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
reducible configuration
discharging method
1, 2, 3-Conjecture
1, 2-Conjecture - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2014, 34, 4; 769-799
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł