On the complexity of vertex-coloring edge-weightingsArticle
Authors: Andrzej Dudek 1; David Wajc 2
NULL##NULL
Andrzej Dudek;David Wajc
1 Department of Mathematics [Kalamazoo]
2 Department of Computer Science [Haifa]
Given a graph G = (V; E) and a weight function omega : E -\textgreater R, a coloring of vertices of G, induced by omega, is defined by chi(omega) (nu) = Sigma(e(sic)nu) omega (e) for all nu is an element of V. In this paper, we show that determining whether a particular graph has a weighting of the edges from \1, 2\ that induces a proper vertex coloring is NP-complete.
Jakub Przybyło;Fan Wei, Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, On asymptotic confirmation of the Faudree-Lehel Conjecture on the irregularity strength of graphs, pp. 766-773, 2023, Prague, Czech Republic, 10.5817/cz.muni.eurocomb23-106.
Mingyue Xiao;Jihui Wang, 2022 International Symposium on Intelligent Robotics and Systems (ISoIRS), The Adjacent Vertex Sum Distinguishing Coloring of the Join and Cartesian Product of Some Digraphs, pp. 143-147, 2022, Chengdu, China, 10.1109/isoirs57349.2022.00036.