The adjacent vertex distinguishing chromatic conjecture
The adjacent vertex distinguishing chromatic conjecture
Let be a simple connected graph, and let 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 and , the sets of colors on edges incident with and are different. The avd-chromatic number is the minimum number of colors in an avd-coloring of .
Zhang's conjecture. If and , where is the cycle of size , then the avd-chromatic number of is at most
Here is the maximum degree of . 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
Sign in to submit a solution.
No solutions have been posted yet.