The general-coloring palette conjecture for complete graphs

About 2 years old · traced to

Let KnK_n be the complete graph on nn vertices, and let τm(n)\tau_m(n) denote the minimum number of colors in an edge-coloring of KnK_n such that all triangles have distinct color palettes, where palettes are multisets of the colors on their three edges. General-coloring palette conjecture. For ngreaterthanorequalto4n greater than or equal to 4,

τm(n)=n−1.\tau_m(n)=n-1.

The preceding theorem establishes the lower bound τm(n)≥n−1\tau_m(n)\geq n-1; the conjecture asserts that this bound is attained for every n≥4n\geq4, extending the exceptional case n=3n=3 where one color suffices.

References

Primary source

Monika Pilsniak and Mariusz Wozniak, “A note on edge colorings distinguishing all triangles in a graph”, arXiv:2407.19050 (2024).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.