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 \} \}$.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.1-12
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01352856
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 16 août 2016 - 15:33:20
Dernière modification le : jeudi 7 septembre 2017 - 01:03:49
Document(s) archivé(s) le : jeudi 17 novembre 2016 - 10:31:33

Fichier

2775-9845-1-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

51

Téléchargements de fichiers

121