Path-factor existence conjecture for graphs without small odd paths

Let k3k\geq 3, and let GG be a graph. For a graph HH, let C(H)\mathcal{C}(H) be the set of components of HH; for i1i\geq 1, let Ci(H)={CC(H)V(C)=i}\mathcal{C}_i(H)=\{C\in\mathcal{C}(H)\mid |V(C)|=i\} and let ci(H)=Ci(H)c_i(H)=|\mathcal{C}_i(H)|. A {P2,P2k+1}\{P_2,P_{2k+1}\}-factor is a spanning subgraph whose components are copies of P2P_2 or P2k+1P_{2k+1}. Path-factor existence conjecture. If

0ik1c2i+1(GX)4k+68k+3X\sum_{0\leq i\leq k-1}c_{2i+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. The conjecture extends the corresponding sufficient conditions known for k=1k=1 and k=2k=2. For k3k\geq 3 divisible by 33, examples show that the analogous bound with an additional constant term cannot guarantee such a factor, while the conjecture proposes that removing this constant term suffices in every case.

Sources & referencesView supporting material

Primary source

Yoshimi Egawa and Michitaka Furuya, “The existence of a path-factor without small odd paths”, arXiv:1503.08556 (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.