Mathematics – Combinatorics
Scientific paper
2010-07-09
Mathematics
Combinatorics
Scientific paper
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_{u\sim 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) \neq 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.
Lu Hongliang
yu Qinglin
Zhang Cun-Quan
No associations
LandOfFree
Vertex-Coloring 2-Edge-Weighting of Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Vertex-Coloring 2-Edge-Weighting of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Vertex-Coloring 2-Edge-Weighting of Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-644564