Girth-forces-dense-bipartite-induced-subgraph conjecture

Let d0d_0 and g0g_0 be constants. A bipartite induced subgraph is an induced subgraph that is bipartite. Girth-induced-subgraph conjecture. There exist d0d_0 and g0g_0 such that any graph of girth at least g0g_0 with minimum degree at least d0d_0 contains a bipartite induced subgraph of minimum degree at least 33. This is a high-girth specialization of the search for dense bipartite induced subgraphs in graphs of large minimum degree. The supplied text gives no resolution.

Sources & referencesView supporting material

Primary source

Louis Esperet, Ross J. Kang and Stéphan Thomassé, “Separation choosability and dense bipartite induced subgraphs”, arXiv:1802.03727 (2018).

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.