Egawa–Furuya conjecture on path-factors and odd components

Let k3k\geq 3 be an integer, let GG be a graph, and for a vertex set XV(G)X\subseteq V(G) let c2j+1(GX)c_{2j+1}(G-X) denote the number of components of GXG-X having order 2j+12j+1. A {P2,P2k+1}P_{2},P_{2k+1}\}-factor is a spanning subgraph whose components are isomorphic to P2P_{2} or P2k+1P_{2k+1}. Egawa–Furuya's conjecture. If

0jk1c2j+1(GX)4k+68k+3X\sum_{0\leq j\leq k-1}c_{2j+1}(G-X)\leq \frac{4k+6}{8k+3}|X|

for all XV(G)X\subseteq V(G), then GG has a {P2,P2k+1}\{P_{2},P_{2k+1}\}-factor. This conjecture was proposed after examples showing that, for k3k\geq 3 with k0(mod3)k\equiv 0\pmod 3, the corresponding bound with an additional constant term cannot generally be improved away; the paper proves the weaker sufficient bound 56k2X\frac{5}{6k^{2}}|X|, but does not resolve the conjectured coefficient.

Sources & referencesView supporting material

Primary source

Yoshimi Egawa, Michitaka Furuya and Kenta Ozeki, “Sufficient conditions for the existence of a path-factor which are related to odd components”, arXiv:1705.08592 (2017).

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.