The adjacent vertex distinguishing chromatic conjecture

From papers

Let GG be a simple connected graph, and let d45ed45e denote its maximum degree. An adjacent vertex distinguishing coloring (or avd-coloring) is a proper edge coloring such that, for every pair of adjacent vertices uu and vv, the sets of colors on edges incident with uu and vv are different. The avd-chromatic number is the minimum number of colors in an avd-coloring of GG.

Zhang's conjecture. If GC5G\neq C_5 and GK2G\neq K_2, where C5C_5 is the cycle of size 55, then the avd-chromatic number of GG is at most

Δ+2.\Delta+2.

Here Δ\Delta is the maximum degree of GG. The conjecture concerns the number of colors required when incident edges must be properly colored while adjacent vertices receive distinct incident color sets; the supplied source gives no evidence of a resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Hamed Hatami, “Δ+300 is a Bound on the Adjacent Vertex Distinguishing Edge Chromatic Number”, arXiv:math/0701012 (2006).

Solutions 0

No solutions have been posted yet.