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

About 8 years old · traced to

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.

References

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.