Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights
Hongliang Lu
Abstract
Let G be a graph and S be
a subset of Z. A vertex-coloring
S-edge-weighting of G is
an assignment of weights by the elements of
S to each edge of G so
that adjacent vertices have different sums of incident edges
weights. It was proved that every 3-connected bipartite graph admits a
vertex-coloring S-edge-weighting for
S={1,2} (H. Lu, Q. Yu
and C. Zhang, Vertex-coloring 2-edge-weighting of graphs, European
J. Combin., 32 (2011), 22-27). In this paper, we show that
every 2-connected and 3-edge-connected bipartite graph admits a
vertex-coloring S-edge-weighting for
S∈
{{0,1},{1,2}}. These
bounds we obtain are tight, since there exists a family of infinite
bipartite graphs which are 2-connected and do not admit
vertex-coloring S-edge-weightings for
S∈{{0,1},{1,2}}.
Full Text: PDF