Conjecture that every extremal graph is complete multipartite
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.