Vertex-coloring graphs with 4-edge-weightings (Q6081387)

An edge-weighting of a graph is called vertex coloring if the weighted degrees yield a proper vertex coloring of the graph. It has been conjectured that for every graph without an isolated edge, a vertex-coloring edge-weighting with the set \(\{1, 2, 3\}\) exists. The paper shows that the statement is true for the weight set \(\{1, 2, 3, 4\}\). The proof is based on the max flow -- min cut theorem.