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

Abstract

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

How to cite

top

Yuehua 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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [11] V.G. Vizing, On an estimate of the chromatic index of a p-graph, Diskret Analiz. 3 (1964) 25-30. 
  12. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.