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

Let GG be a graph on 4t14t-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 t22t\leq22, while the general case remains open; a counterexample would also imply a counterexample to Hadwiger's conjecture.

Sources & referencesView supporting material

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.