Geodesic
Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six
Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 3, pp. 429-439.

Voir la notice de l'article provenant de la source Library of Science

An adjacent vertex distinguishing edge-coloring of a graph G is a proper edge-coloring o G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring of G is denoted by χ'ₐ(G). We prove that χ'ₐ(G) is at most the maximum degree plus 2 if G is a planar graph without isolated edges whose girth is at least 6. This gives new evidence to a conjecture proposed in [Z. Zhang, L. Liu, and J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett., 15 (2002) 623-626.]
Keywords: edge-coloring, vertex-distinguishing, planar graph 
@article{DMGT_2011_31_3_a1,
     author = {Bu, Yuehua and Lih, Ko-Wei and Wang, Weifan},
     title = {Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {429--439},
     publisher = {mathdoc},
     volume = {31},
     number = {3},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a1/}
}
TY  - JOUR
AU  - Bu, Yuehua
AU  - Lih, Ko-Wei
AU  - Wang, Weifan
TI  - Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2011
SP  - 429
EP  - 439
VL  - 31
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a1/
LA  - en
ID  - DMGT_2011_31_3_a1
ER  - 
%0 Journal Article
%A Bu, Yuehua
%A Lih, Ko-Wei
%A Wang, Weifan
%T Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six
%J Discussiones Mathematicae. Graph Theory
%D 2011
%P 429-439
%V 31
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a1/
%G en
%F DMGT_2011_31_3_a1
Bu, Yuehua; Lih, Ko-Wei; Wang, Weifan. Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six. Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 3, pp. 429-439. http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a1/

[1] M. Aigner, E. Triesch and Z. Tuza, Irregular assignments and vertex-distinguishing edge-colorings of graphs, in: Proceedings of Combinatorics '90, A. Barlotti et al., eds. (North-Holland, Amsterdam, 1992) 1-9.

[2] S. Akbari, H. Bidkhori and N. Nosrati, r-Strong edge colorings of graphs, Discrete Math. 306 (2006) 3005-3010, doi: 10.1016/j.disc.2004.12.027.

[3] P.N. Balister, E. Gyori, J. Lehel and R. H. Schelp, Adjacent vertex distinguishing edge-colorings, SIAM J. Discrete Math. 21 (2007) 237-250, doi: 10.1137/S0895480102414107.

[4] P.N. Balister, O.M. Riordan and R.H. Schelp, Vertex-distinguishing edge colorings of graphs, J. Graph Theory 42 (2003) 95-109, doi: 10.1002/jgt.10076.

[5] J.-L. Baril, H. Kheddouci and O. Togni, Adjacent vertex distinguishing edge-colorings of meshes, Australas. J. Combin. 35 (2006) 89-102.

[6] J.-L. Baril and O. Togni, Neighbor-distinguishing k-tuple edge-colorings of graphs, Discrete Math. 309 (2009) 5147-5157, doi: 10.1016/j.disc.2009.04.003.

[7] A.C. Burris and R.H. Schelp, Vertex-distinguishing proper edge-colorings, J. Graph Theory 26 (1997) 70-82, doi: 10.1002/(SICI)1097-0118(199710)26:273::AID-JGT2>3.0.CO;2-C

[8] K. Edwards, M. Hornák and M. Woźniak, On the neighbour-distinguishing index of a graph, Graphs Combin. 22 (2006) 341-350, doi: 10.1007/s00373-006-0671-2.

[9] O. Favaron, H. Li and R.H. Schelp, Strong edge colorings of graphs, Discrete Math. 159 (1996) 103-109, doi: 10.1016/0012-365X(95)00102-3.

[10] H. Hatami, Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number, J. Combin. Theory (B) 95 (2005) 246-256, doi: 10.1016/j.jctb.2005.04.002.

[11] V.G. Vizing, On an estimate of the chromatic index of a p-graph, Diskret Analiz. 3 (1964) 25-30.

[12] Z. Zhang, L. Liu and J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623-626, doi: 10.1016/S0893-9659(02)80015-5.