Fox–Pach sharp edge bound conjecture for K_{t,t}-free string graphs
Fox–Pach sharp edge bound conjecture for K_{t,t}-free string graphs
From papers
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Jacob Fox and Janos Pach, “Applications of a new separator theorem for string graphs”, arXiv:1302.7228 (2013).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.