Hongliang Lu - Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights

dmtcs:2162 - Discrete Mathematics & Theoretical Computer Science, January 5, 2016, Vol. 17 no. 3 - https://doi.org/10.46298/dmtcs.2162
Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge WeightsArticle

Authors: Hongliang Lu 1

  • 1 School of Mathematics and Statistics, Xi’an Jiaotong University

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 weights 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 $\mathcal{S}$-edge-weighting for $\mathcal{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 $\mathcal{S}$-edge-weighting for $\mathcal{S} \in \{ \{ 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 $\mathcal{S}$-edge-weightings for $\mathcal{S} \in \{ \{ 0,1 \} , \{1,2 \} \}$.


Volume: Vol. 17 no. 3
Section: Graph Theory
Published on: January 5, 2016
Submitted on: February 28, 2015
Keywords: 2-connected, bipartite grap,edge-weighting, vertex-coloring,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 390 times.
This article's PDF has been downloaded 423 times.