Thomassen's conjecture on dense bipartite subgraphs of large girth
Thomassen's conjecture on dense bipartite subgraphs of large girth
Let . A bipartite graph has average degree at least if its average degree is at least the value of a function .
Thomassen's conjecture. There is a function such that, for all , every bipartite graph of average degree at least has a subgraph of average degree at least and girth at least .
This is a conjecture about finding arbitrarily dense subgraphs of arbitrarily large prescribed girth in bipartite graphs. The paper notes that the case of girth is currently the best known.
Sources & referencesView supporting material
Primary source
Rose McCarty, “Dense induced subgraphs of dense bipartite graphs”, arXiv:2004.00035 (2020).
Additional references
3 papers in this index state this conjecture (2013–2020). The statement above is taken from the most recent of them; the others are arXiv:1403.1995, arXiv:1303.4982.
Source: https://arxiv.org/abs/2004.00035 Thomassen (1983), source attribution in the paper
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.