Vertex-Coloring 2-Edge-Weighting of Graphs

Hongliang Lu, Qinglin Yu, Cun-Quan Zhang

A $k$-{\it edge-weighting} $w$ of a graph $G$ is an assignment of an integer weight, $w(e)\in \{1,\dots ,k\}$, to each edge $e$. An edge weighting naturally induces a vertex colori…