Résumé | An adjacent vertex-distinguishing edge coloring (AVD coloring) of a graph is a proper edge coloring such that no two
neighbors are incident to the same set of colors. Zhang et al. conjectured that every connected graph on at least 6 vertices is AVD (Delta+2)-colorable, where Delta is the maximum degree.
In this talk, we prove that (Delta+1) colors are enough when Delta is sufficiently larger than the maximum average degree, denoted mad.
We also provide more precise lower bounds for two graph classes: planar graphs, and graphs with mad<3. In the first case, Delta>=12 suffices, which generalizes the result of Edwards on planar bipartite graphs and strengthens the result of Hornak et al. that (Delta+2) is enough. In the second case, Delta>=4 is enough, which is optimal and completes the results of Wang and Wang and of Hocquard and Montassier.
|