A note on a directed version of the 1-2-3 Conjecture

作者：Hornak Mirko; Przybylo Jakub^*; Wozniak Mariusz

来源：Discrete Applied Mathematics, 2018, 236: 472-476.

DOI：10.1016/j.dam.2017.11.016

• Edge coloring
• Digraph
• 1-2-3 Conjecture

The least k such that a given digraph D = (V, A) can be arc-labeled with integers in the interval [1, k] so that the sum of values in-coming to x is distinct from the sum of values out-going from y for every arc (x, y) epsilon A, is denoted by (chi) over bar (e)((sis))(D). This corresponds to one of possible directed versions of the well-known 1-2-3 Conjecture. Unlike in the case of other possibilities, we show that (chi) over bar (e)((sis))(D) is unbounded in the family of digraphs for which this parameter is well defined. However, if the family is restricted by excluding the digraphs with so-called lonely arcs, we prove that (chi) over bar (e)((sis))(D) <= 4, and we conjecture that (chi) over bar (e)((sis))(D) <= 3 should hold.

• 出版日期2018-2-19