Generalized weak-subdivision conjecture for complete graphs
Generalized weak-subdivision conjecture for complete graphs
Let be a graph with vertices, and let denote its complement. An induced weak-subdivision of is an induced subgraph of obtained by the weak-subdivision operation applied to the complete graph ; a bi-clique is a complete bipartite subgraph.
Generalized weak-subdivision conjecture. For every and integer , there exists such that, if has at most
edges and does not contain an induced weak-subdivision of , then contains a bi-clique of size at least .
The conjecture generalizes the proved case discussed immediately beforehand and is stated as sharp in the source: examples formed from clique parts can have nearly the threshold number of edges while their complements have no linear-sized bi-clique. The supplied text does not indicate that the general case has been resolved.
Sources & referencesView supporting material
Primary source
Istvan Tomon, “A sharp threshold phenomenon in string graphs”, arXiv:1908.05550 (2019).
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.