Conjecture that every extremal graph is complete multipartite
Let be a non-increasing sequence of natural numbers, and let a graph be -extremal if it attains the maximum number of -valid edge-colourings among graphs on 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 , every -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.
References
Primary source
Oleg Pikhurko and Katherine Staden, “Stability for the Erdős-Rothschild problem”, arXiv:2105.09991 (2023).
Progress summary
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.