The general-coloring palette conjecture for complete graphs

From papers

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)=n1.\tau_m(n)=n-1.

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

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

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

Solutions 0

No solutions have been posted yet.