The linear-length monochromatic cycle conjecture for dense graphs

Let GG be a graph of sufficiently large order nn, and let 0<c<10<c<1. A 22-coloring of E(G)E(G) assigns each edge of GG one of two colors, red or blue. A monochromatic cycle is a cycle all of whose edges receive the same color.

Linear-length monochromatic cycle conjecture. If

δ(G)>cn,\delta(G)>cn,

then every 22-coloring of E(G)E(G) contains a monochromatic cycle CkC_k for some kcnk\geq cn.

This is presented as a seemingly easier conjecture than the preceding cycle-interval conjecture. It asks whether a positive minimum-degree proportion alone forces a monochromatic cycle whose length is at least the same linear proportion of the order; the source gives no resolution status.

Sources & referencesView supporting material

Primary source

Hao Li, Vladimir Nikiforov and Richard Schelp, “A new type of Ramsey-Turan problems”, arXiv:1001.2078 (2010).

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.