|
For a given graph $G=(V,E)$, an $\{a,b\}$-edge-weighting is an assignment $w: E\rightarrow\{a,b\}$, which we call proper if the induced labeling $z:V\rightarrow\Z$ is a proper vertex coloring of $G$, where $a,b$ are distinct integers and $z(v)=\sum_{e\in\Delta(v)}w(e)$.
Dudek and Wajc~\cite{dudek2011complexity} proved that deciding whether a given graph $G$ has a proper $\{1,2\}$-edge-weighting is NP-complete.
Strengthening their result, we show that the problem is NP-complete for any distinct integers $a$ and $b$.
Thomassen, Wu and Zhang~\cite{thomassen20163} gave a polynomial-time algorithm to decide whether a given bipartite graph has a proper $\{1,2\}$-edge-weighting. We consider a natural generalization of this problem when a partial edge-weighting is to be extended, which is shown to be NP-complete for any distinct integers $a,b$. We also prove that the problem is solvable in polynomial time for trees.
Bibtex entry:
| AUTHOR | = | {Madarasi, P{\'e}ter and Simon, M{\'a}t{\'e}}, |
| TITLE | = | {On vertex-coloring $\{a,b\}$-edge-weightings of graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2022}, |
| NUMBER | = | {TR-2022-06} |