Axenovich–Martin conjecture on complete partitions of bipartite-free graphs
Axenovich–Martin conjecture on complete partitions of bipartite-free graphs
Let be a bipartite graph that is not a forest. Write for the least integer such that every -free -graph does not exist, and write for the maximum number of edges in an -free graph on vertices. An -free -graph is a graph whose vertex set is partitioned into parts of size at most , with at least one edge between every two parts. Axenovich–Martin conjecture. There is a positive constant such that for any positive integers and satisfying
there is an -free -graph, equivalently . If true, this would show that the trivial lower bound gives the correct order of magnitude and remove the logarithmic factor from the known upper bound for .
Sources & referencesView supporting material
Primary source
John Byrne, Michael Tait and Craig Timmons, “Forbidden subgraphs and complete partitions”, arXiv:2308.16728 (2025).
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.