{"id":"arxiv/2609.31205","url":"https://arxiv.org/abs/2609.31205","tags":["cs.DM","cs.CC","math.CO"],"score":0,"title":"Complexity, approximation, and extension of proper $\\{a,b\\}$-edge-weightings","domain":"cs.DM","source":"arxiv","authors":["Péter Madarasi","Máté Simon"],"reviews":0,"subject":"cs.DM","summary":"For distinct integers $a$ and $b$, an $\\{a,b\\}$-edge-weighting assigns $a$ or $b$ to each edge and labels each vertex by the sum of its incident weights. Such a weighting is proper if adjacent vertices receive distinct labels. We prove that, for every fixed pair of distinct integers, deciding whether a proper weighting exists is NP-complete even for simple cubic planar graphs. On planar multigraphs with $m$ edges, we give an exact $2^{O(\\sqrt m)}$-time algorithm and, assuming the Exponential Time Hypothesis (ETH), exclude $2^{o(\\sqrt m)}$-time algorithms even for simple cubic planar graphs.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{}}