Fox–Pach sharp edge bound conjecture for K_{t,t}-free string graphs
For an integer , a graph is -free if it contains no complete bipartite subgraph with vertices in each part. Fox–Pach's sharp edge bound conjecture. Every -free string graph on vertices has at most
edges, for an absolute constant . The weaker linear bound is known with , while this estimate is conjectured to be best possible.
References
Primary source
Jacob Fox and Janos Pach, “Applications of a new separator theorem for string graphs”, arXiv:1302.7228 (2013).
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.