Five-color conjecture for majority distinguishing edge colorings

From papers

Let GG be a graph of minimum degree at least 22 that has a connected asymmetric spanning subgraph. A majority distinguishing edge coloring of GG assigns colors to the edges so that each color appears on at most half of the edges incident with every vertex, and only the identity automorphism of GG preserves the coloring.

Five-color conjecture. Every such graph GG has a majority distinguishing edge 55-coloring.

The conjecture would improve the preceding general bound of seven colors for graphs with a connected asymmetric spanning subgraph. The source does not provide evidence that the conjecture has been resolved.

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

Aleksandra Gorzkowska and Magdalena Prorok, “Majority distinguishing edge coloring”, arXiv:2312.05564 (2023).

Solutions 0

No solutions have been posted yet.