Geodesic
Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights
Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 3.

Voir la notice de l'article provenant de la source Episciences

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 \} \}$. 
@article{DMTCS_2016_17_3_a18,
     author = {Lu, Hongliang},
     title = {Vertex-Coloring {Edge-Weighting} of {Bipartite} {Graphs} with {Two} {Edge} {Weights}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {17},
     number = {3},
     year = {2015-2016},
     doi = {10.46298/dmtcs.2162},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2162/}
}
TY  - JOUR
AU  - Lu, Hongliang
TI  - Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights
JO  - Discrete mathematics & theoretical computer science
PY  - 2015-2016
VL  - 17
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2162/
DO  - 10.46298/dmtcs.2162
LA  - en
ID  - DMTCS_2016_17_3_a18
ER  - 
%0 Journal Article
%A Lu, Hongliang
%T Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights
%J Discrete mathematics & theoretical computer science
%D 2015-2016
%V 17
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2162/
%R 10.46298/dmtcs.2162
%G en
%F DMTCS_2016_17_3_a18
Lu, Hongliang. Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights. Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 3. doi : 10.46298/dmtcs.2162. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2162/

Cité par Sources :