Ryjáček's conjecture on locally connected graphs

A finite, simple, undirected graph GG is locally connected if, for every vertex uu of GG, the subgraph induced by the neighborhood NG(u)N_G(u) is connected. It is weakly pancyclic if it has a cycle of every order \ell between its girth g(G)g(G) and circumference c(G)c(G).

Ryjáček's conjecture. Every locally connected graph is weakly pancyclic.

This conjecture proposes that local connectivity forces a graph to contain cycles of all orders between its shortest and longest cycle. The source states it as motivation for the paper; no resolution is supplied here.

Sources & referencesView supporting material

Primary source

Christoph Brause, Dieter Rautenbach and Ingo Schiermeyer, “Local Connectivity, Local Degree Conditions, some Forbidden Induced Subgraphs, and Cycle Extendability”, arXiv:1507.07486 (2015).

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.