Füredi–Gyárfás–Simonyi conjecture on connected matchings

About 5 years old · traced to

Let GG be a graph on 4t−14t-1 vertices with independence number α(G)=2\alpha(G)=2. A connected matching is a matching whose edges are pairwise linked by edges of GG; write cm⁡(G)\operatorname{cm}(G) for the size of a largest connected matching.

Füredi–Gyárfás–Simonyi conjecture.

cm⁡(G)≥t.\operatorname{cm}(G)\geq t.

This conjecture is a precise version of the problem of determining the largest connected matching in graphs with independence number two. The paper reports that it is known for t≤22t\leq22, while the general case remains open; a counterexample would also imply a counterexample to Hadwiger's conjecture.

References

Primary source

Rong Chen and Zijian Deng, “Connected matching in graphs with independence number two”, arXiv:2409.05920 (2024).

Additional references

2 papers in this index state this conjecture (2021–2024). The statement above is taken from the most recent of them; the others are arXiv:2108.10303.

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.