Girth-forces-dense-bipartite-induced-subgraph conjecture
Girth-forces-dense-bipartite-induced-subgraph conjecture
Let and be constants. A bipartite induced subgraph is an induced subgraph that is bipartite. Girth-induced-subgraph conjecture. There exist and such that any graph of girth at least with minimum degree at least contains a bipartite induced subgraph of minimum degree at least . 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
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.