The set-palette conjecture for complete graphs
Let be the complete graph on vertices. In a general edge-coloring of , let denote the minimum number of colors needed so that all triangles have distinct color palettes when a palette is viewed as the set of colors appearing on its three edges. Set-palette conjecture. For ,
The source notes the inequality and states that this conjecture would imply the preceding multiset-palette conjecture. Its status is not resolved in the supplied text.
References
- Monika Pilsniak and Mariusz Wozniak, “A note on edge colorings distinguishing all triangles in a graph”, arXiv:2407.19050 (2024).
Progress summary
A dated submission claims the conjecture is false already for five vertices, but this counterexample has not been independently validated.
The conjecture of Monika Pilśniak and Mariusz Woźniak, introduced in 2024, asserts that the minimum number of colors needed to distinguish all triangle color-sets in a complete graph is for every .
Known results
- Pilśniak and Woźniak (2024) prove for .
- They establish .
- For proper edge-colorings, they prove when is odd and when is even.
- Their examples for and do not settle the set-palette conjecture.
Community submission (unverified)
A submission dated November 7, 2026 argues that every edge-coloring of using a set of colors has two distinct triangles with the same color-set, which would refute the conjecture at . The argument is presented as a complete proof, but remains unverified.
Current status (as of November 2026): The conjecture is unsettled; a community submission claims a counterexample at , but that claim is unverified.
Sources
Solutions 1
No four-label edge coloring of K5 distinguishes all triangles by color setsSee full solution
Result and scope. Every map E(K5)->Fin 4 has two distinct triangles with equal edge-color sets; refutes Pilsniak-Wozniak arXiv:2407.19050v1 Conjecture 5 (tau_s(n)=n-1 for all n>=4) at n=5. Multiset Conjecture 4 untouched.
Complete proof: No four-label edge coloring of K5 distinguishes all triangles by color sets · PDF.
The paper page contains the supplementary proof-source JSON and extract_sources.py. The linked paper supplies the complete argument and states the precise scope of the Lean certificate, ordinary proofs, supporting computations, and source interpretation. Those qualifications are retained here; a supporting computation is not a proof of a broader statement.
This is an AI-assisted research preprint. Internal review is not external journal peer review. Bounded prior-art searches do not establish worldwide priority. See the paper for formalization and trust limits.