On vertex-coloring edge-weighting of graphs
发布时间：2025-04-30
点击次数：
- 发布时间：
- 2025-04-30
- 论文名称：
- On vertex-coloring edge-weighting of graphs
- 发表刊物：
- Front. Math. China
- 摘要：
- 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 coloring $c$ by defining $c(u)=sum_{usim e} w(e)$ for every $u in V(G)$. A $k$-edge-weighting of a graph $G$ is emph{vertex-coloring} if the induced coloring $c$ is proper, i.e., $c(u)
eq c(v)$ for any edge $uv in E(G)$.
Given a graph $G$ and a vertex coloring $c_0$, does there exist an edge-weighting such that the induced vertex coloring is $c_0$? 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 cite{KLT}. 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.
- 合写作者：
- H. Lu, X. Yang and Q. Yu
- 卷号：
- 4
- 页面范围：
- 325-334
- 是否译文：
- 否
- 发表时间：
- 2009-03-03