# Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six

Yuehua Bu; Ko-Wei Lih; Weifan Wang

Discussiones Mathematicae Graph Theory (2011)

- Volume: 31, Issue: 3, page 429-439
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topYuehua Bu, Ko-Wei Lih, and Weifan Wang. "Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six." Discussiones Mathematicae Graph Theory 31.3 (2011): 429-439. <http://eudml.org/doc/271040>.

@article{YuehuaBu2011,

abstract = {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.]},

author = {Yuehua Bu, Ko-Wei Lih, Weifan Wang},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {edge-coloring; vertex-distinguishing; planar graph},

language = {eng},

number = {3},

pages = {429-439},

title = {Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six},

url = {http://eudml.org/doc/271040},

volume = {31},

year = {2011},

}

TY - JOUR

AU - Yuehua Bu

AU - Ko-Wei Lih

AU - Weifan Wang

TI - Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six

JO - Discussiones Mathematicae Graph Theory

PY - 2011

VL - 31

IS - 3

SP - 429

EP - 439

AB - 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.]

LA - eng

KW - edge-coloring; vertex-distinguishing; planar graph

UR - http://eudml.org/doc/271040

ER -

## References

top- [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. Zbl0769.05035
- [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. Zbl1189.05056
- [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. Zbl1008.05067
- [5] J.-L. Baril, H. Kheddouci and O. Togni, Adjacent vertex distinguishing edge-colorings of meshes, Australas. J. Combin. 35 (2006) 89-102. Zbl1108.05035
- [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. Zbl1179.05041
- [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:2<73::AID-JGT2>3.0.CO;2-C Zbl0886.05068
- [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. Zbl1107.05032
- [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. Zbl0859.05042
- [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. Zbl1075.05034
- [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. Zbl1008.05050

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.