287Accesses
49Citations
Abstract
An adjacent vertex distinguishing edge-coloring of a graphG is a proper edge coloring ofG 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 ofG is denoted byχ′a(G). Let\(\mathop{\mathrm{mad}}(G)\) andΔ denote the maximum average degree and the maximum degree of a graphG, respectively.
In this paper, we prove the following results: (1) If\(\mathop{\mathrm{mad}}(G)<3\) andΔ≥3, thenχ′a(G)≤Δ+2. (2) If\(\mathop{\mathrm{mad}}(G)<\frac{5}{2}\) andΔ≥4, or\(\mathop{\mathrm{mad}}(G)<\frac{7}{3}\) andΔ=3, thenχ′a(G)≤Δ+1. (3) If\(\mathop{\mathrm{mad}}(G)<\frac{5}{2}\) andΔ≥5, thenχ′a(G)=Δ+1 if and only ifG contains adjacent vertices of maximum degree.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
References
Aigner M, Triesch E, Tuza Z (1992) Irregular assignments and vertex-distinguishing edge-colorings of graphs. In: Barlotti A et al. (eds) Proceedings of combinatorics ’90. North-Holland, Amsterdam, pp 1–9
Akbari S, Bidkhori H, Nosrati N (2006)r-Strong edge colorings of graphs. Discrete Math 306:3005–3010
Balister PN, Riordan OM, Schelp RH (2003) Vertex-distinguishing edge colorings of graphs. J Graph Theory 42:95–109
Balister PN, Győri E, Lehel J, Schelp RH (2007) Adjacent vertex distinguishing edge-colorings. SIAM J Discrete Math 21:237–250
Bu Y, Lih K-W, Wang W (2007) Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six. Submitted
Burris AC, Schelp RH (1997) Vertex-distinguishing proper edge-colorings. J Graph Theory 26:70–82
Favaron O, Li H, Schelp RH (1996) Strong edge colorings of graphs. Discrete Math 159:103–109
Hatami H (2005)Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number. J Comb Theory Ser B 95:246–256
Montassier M, Raspaud A (2006) (d,1)-Total labeling of graphs with a given maximum average degree. J Graph Theory 51:93–109
Vizing VG (1964) On an estimate of the chromatic index of ap-graph. Diskret Anal 3:25–30
Zhang Z, Liu L, Wang J (2002) Adjacent strong edge coloring of graphs. Appl Math Lett 15:623–626
Author information
Authors and Affiliations
Department of Mathematics, Zhejiang Normal University, Zhejiang, Jinhua, 321004, China
Weifan Wang & Yiqiao Wang
- Weifan Wang
You can also search for this author inPubMed Google Scholar
- Yiqiao Wang
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toWeifan Wang.
Additional information
Research supported partially by NSFC (No. 10771197).
Rights and permissions
About this article
Cite this article
Wang, W., Wang, Y. Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree.J Comb Optim19, 471–485 (2010). https://doi.org/10.1007/s10878-008-9178-5
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative