2013/07/07 by Hongliang Lu, Lu, Hongliang
Mathematics · #05C15 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15
paper · pdf · doi:10.48550/arxiv.1307.1863
In this paper, we show that every 2-connected and 3-edge-connected bipartite graph admits a vertex-coloring S-edge-weighting for S\in {{0,1},{1,2}}
arxiv created 2013/07/07 · arxiv updated 2013/07/09
Let G be a graph and \mathcal S be a subset of Z. A vertex-coloring \mathcal S-edge-weighting of G is an assignment of weight s by the elements of \mathcal 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 \1,2\-edge-weighting (Lu, Yu and Zhang, (2011) \citeLYZ). In this paper, we show that the following result: if a 3-edge-connected bipartite graph G with minimum degree δ contains a vertex u∈ V(G) such that dG(u)=δ and G-u is connected, then G admits a vertex-coloring \mathcal S-edge-weighting for \mathcal S∈ \\0,1\,\1,2\\. In particular, we show that every 2-connected and 3-edge-connected bipartite graph admits a vertex-coloring \mathcal S-edge-weighting for \mathcal S∈ \\0,1\,\1,2\\. The bound is sharp, since there exists a family of infinite bipartite graphs which are 2-connected and do not admit vertex-coloring \1,2\-edge-weightings or vertex-coloring \0,1\-edge-weightings.