| Autor: |
Baudon Olivier, Bensmail Julien, Sopena Éric |
| Jazyk: |
angličtina |
| Rok vydání: |
2015 |
| Předmět: |
|
| Zdroj: |
Discussiones Mathematicae Graph Theory, Vol 35, Iss 1, Pp 141-156 (2015) |
| Druh dokumentu: |
article |
| ISSN: |
2083-5892 |
| DOI: |
10.7151/dmgt.1791 |
| Popis: |
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 −G⃗ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of −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 NP-complete problem. These results also hold for product or list versions of this problem. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
