- Tytuł:
- An Oriented Version of the 1-2-3 Conjecture
- Autorzy:
-
Baudon, Olivier
Bensmail, Julien
Sopena, Éric - Powiązania:
- https://bibliotekanauki.pl/articles/31339138.pdf
- Data publikacji:
- 2015-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
oriented graph
neighbour-sum-distinguishing arc-weighting
complexity
1-2-3 Conjecture - Opis:
- The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph $G$ with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of $G$. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph \(\overrightarrow{G}\) can be assigned weights from {1, 2, 3} so that every two adjacent vertices of \(\overrightarrow{G}\) receive distinct sums of outgoing weights. This result is tight in the sense that some oriented graphs do not admit such an assignment using the weights from {1, 2} only. We finally prove that deciding whether two weights are sufficient for a given oriented graph is an $\mathsf{NP}$-complete problem. These results also hold for product or list versions of this problem.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2015, 35, 1; 141-156
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł