Esperet–Kang–Thomassé conjecture on dense induced bipartite subgraphs
Statement
Let be a positive real number, and let be a triangle-free graph with minimum degree at least . An induced bipartite subgraph of is a bipartite subgraph induced by a subset of the vertices of , and its average degree is the average of its vertex degrees. Esperet–Kang–Thomassé conjecture. The graph contains an induced bipartite subgraph with average degree
This conjecture strengthens the known bound of order proved for every triangle-free graph of minimum degree . It asks whether the logarithmic factor can be achieved without the additional loss.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.