TR-2022-06

On vertex-coloring $\{a,b\}$-edge-weightings of graphs

Péter Madarasi, Máté Simon



Abstract

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:

@techreport{egres-22-06,
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}
}


Last modification: 21.3.2024. Please email your comments to Tamás Király!