The monochromatic cycle interval conjecture for dense 2-colored graphs

Let GG be a graph of order nn, with vertex set V(G)V(G) and edge set E(G)E(G). A 22-coloring of GG is a partition

E(G)=E(R)E(B),E(G)=E(R)\cup E(B),

where RR and BB are spanning subgraphs of GG. Write CkRC_k\subset R or CkBC_k\subset B when the red or blue graph contains a cycle of length kk.

Monochromatic cycle interval conjecture. If n4n\geq4 and δ(G)>3n/4\delta(G)>3n/4, then every 22-coloring of E(G)E(G) has, for every k[4,n/2]k\in[4,\lceil n/2\rceil], either a red kk-cycle or a blue kk-cycle:

CkR or CkBfor all k[4,n/2].C_k\subset R\text{ or }C_k\subset B\quad\text{for all }k\in[4,\lceil n/2\rceil].

This proposes a Ramsey--Turán strengthening of results for complete graphs and very dense graphs: a minimum-degree condition should force monochromatic cycles of every length in a whole interval, rather than merely one cycle length. The source gives no resolution status for the conjecture.

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.