Conjecture that every extremal graph is complete multipartite

Let k=(k1,...,ks)\bm{k}=(k_1,\hspace{0.9pt}.\hspace{0.3pt}.\hspace{0.3pt}.\hspace{1.5pt},k_s) be a non-increasing sequence of natural numbers, and let a graph be k\bm{k}-extremal if it attains the maximum number F(n;k)F(n;\bm{k}) of k\bm{k}-valid edge-colourings among graphs on nn vertices. A graph is complete multipartite if its vertex set can be partitioned into parts such that every pair of vertices in distinct parts is adjacent. Extremal multipartite conjecture. For every k\bm{k}, every k\bm{k}-extremal graph is complete multipartite. At least one extremal graph is known to be complete multipartite, but the conjecture asserts this for every extremal graph.

Sources & referencesView supporting material

Primary source

Oleg Pikhurko and Katherine Staden, “Stability for the Erdős-Rothschild problem”, arXiv:2105.09991 (2023).

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.