2010/07/09 by Hongliang Lu, Qinglin Yu, Lu, Hongliang +4
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1007.1505
openalex publication_date 2010/07/09 · arxiv created 2010/07/12 · arxiv updated 2010/07/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A k-\it edge-weighting w of a graph G is an assignment of an integer weight, w(e)∈ \1,…, k\, to each edge e. An edge weighting naturally induces a vertex coloring c by defining c(u)=∑u∼ e w(e) for every u ∈ V(G). A k-edge-weighting of a graph G is vertex-coloring if the induced coloring c is proper, i.e., c(u) ≠ c(v) for any edge uv ∈ E(G). Given a graph G and a vertex coloring c0, does there exist an edge-weighting such that the induced vertex coloring is c0? We investigate this problem by considering edge-weightings defined on an abelian group. It was proved that every 3-colorable graph admits a vertex-coloring 3-edge-weighting \citeKLT. Does every 2-colorable graph (i.e., bipartite graphs) admit a vertex-coloring 2-edge-weighting? We obtain several simple sufficient conditions for graphs to be vertex-coloring 2-edge-weighting. In particular, we show that 3-connected bipartite graphs admit vertex-coloring 2-edge-weighting.