zbMATH — the first resource for mathematics

Adjacent vertex-distinguishing edge coloring of 2-degenerate graphs. (English) Zbl 1342.90215
Summary: The adjacent vertex-distinguishing chromatic index \(\chi'_{\mathrm{avd}}(G)\) of a graph \(G\) is the smallest integer \(k\) for which \(G\) admits a proper edge \(k\)-coloring such that no pair of adjacent vertices are incident with the same set of colors. In this paper, we prove that if \(G\) is a \(2\)-degenerate graph without isolated edges, then \(\chi'_{\mathrm{avd}}(G)\leq\max\{6,\Delta (G)+1\}\). Moreover, we also show that when \(\Delta\geq 6\), \(\chi'_{\mathrm{avd}}=\Delta (G)+1\) if and only if \(G\) contains two adjacent vertices of maximum degree.

90C35 Programming involving graphs or networks
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Balister, PN; Győri, E; Lehel, J; Schelp, RH, Adjacent vertex-distinguishing edge-coloring, SIAM J. Discret. Math., 21, 237-250, (2007) · Zbl 1189.05056
[2] Bonamy, M; Bousquet, N; Hocquard, H, Adjacent vertex-distinguishing edge coloring of graphs, EuroComb, 16, 313-318, (2013) · Zbl 1291.05055
[3] Bu, Y; Lih, K-W; Wang, W, Adjacent vertex-distinguishing edge-colorings of planar graphs with girth at least six, Discuss. Math. Graph Theory, 31, 429-439, (2011) · Zbl 1229.05100
[4] Edwards, K; Horňák, M; Woźniak, M, On the neighbour-distinguishing index of a graph, Graphs Comb., 22, 341-350, (2006) · Zbl 1107.05032
[5] Hatami, H, \(Δ \)+ 300 is a bound on the adjacent vertex-distinguishing edge chromatic number, J. Comb. Theory Ser. B, 95, 246-256, (2005) · Zbl 1075.05034
[6] Hocquard, H; Montassier, M, Adjacent vertex-distinguishing edge coloring of graphs with maximum degree \(Δ \), J. Comb. Optim., 26, 152-160, (2013) · Zbl 1276.90079
[7] Horňák, M; Huang, D; Wang, W, On neighbor-distinguishing index of planar graphs, J. Graph Theory, 76, 262-278, (2014) · Zbl 1296.05072
[8] Vizing, VG, Critical graphs with a given chromatic index (in Russian), Diskret. Anal., 5, 9-17, (1965) · Zbl 0171.44902
[9] Wang, W; Wang, Y, Adjacent vertex-distinguishing edge-colorings of graphs with smaller maximum average degree, J. Comb. Optim., 19, 471-485, (2010) · Zbl 1221.05166
[10] Wang, W; Wang, Y, Adjacent vertex-distinguishing edge coloring of \(K_4\)-minor free graphs, Appl. Math. Lett., 24, 2034-2037, (2011) · Zbl 1234.05105
[11] Zhang, Z; Liu, L; Wang, J, Adjacent strong edge coloring of graphs, Appl. Math. Lett., 15, 623-626, (2002) · Zbl 1008.05050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.