ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let dd be a positive real number, and let GG be a triangle-free graph with minimum degree at least dd. An induced bipartite subgraph of GG is a bipartite subgraph induced by a subset of the vertices of GG, and its average degree is the average of its vertex degrees. Esperet–Kang–Thomassé conjecture. The graph GG contains an induced bipartite subgraph with average degree

Ω(ln⁡d).\Omega(\ln d).

This conjecture strengthens the known bound of order ln⁡d/ln⁡ln⁡d\ln d/\ln\ln d proved for every triangle-free graph of minimum degree dd. It asks whether the logarithmic factor can be achieved without the additional ln⁡ln⁡d\ln\ln d 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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.