Skip to Main content Skip to Navigation
Journal articles

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

Abstract : 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 \} \}$.
Document type :
Journal articles
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-01352856
Contributor : Coordination Episciences Iam <>
Submitted on : Tuesday, August 16, 2016 - 3:33:20 PM
Last modification on : Wednesday, June 10, 2020 - 10:00:04 AM
Long-term archiving on: : Thursday, November 17, 2016 - 10:31:33 AM

File

2775-9845-1-PB.pdf
Explicit agreement for this submission

Identifiers

  • HAL Id : hal-01352856, version 1

Collections

Citation

Hongliang Lu. Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.1-12. ⟨hal-01352856⟩

Share

Metrics

Record views

123

Files downloads

908