Maximum square-free 2-matching

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple undirected graph. A $2$-matching is a subset $F\subseteq E$ satisfying $d_F(v)\le2$ at every vertex. Thus each nontrivial component of $(V,F)$ is a path or a cycle, and isolated vertices are allowed. Call $F$ square-free if $(V,F)$ contains no cycle with exactly four edges.

The problem asks for a deterministic polynomial-time algorithm computing \[ \nu^{\mathrm{sq}}_2(G)= \max\{|F|:F\subseteq E,\ d_F(v)\le2\ (v\in V), \ (V,F)\text{ has no }4\text{-cycle}\}, \] and producing an attaining edge set. The graph is unrestricted: it need not be bipartite or have bounded maximum degree.

Only the selected edge set is forbidden to contain a square. A four-cycle present in the original graph causes no violation if at least one of its edges is omitted. Triangles and cycles of length five or more are permitted, so requiring every selected cycle to have length at least five is a distinct problem. Every edge has unit value; a weighted version with arbitrary edge weights imposes a different optimization task. Finally, maximum cardinality is stronger than inclusion-wise maximality: being unable to add one edge does not certify that the chosen square-free $2$-matching has optimum size.

Short English statement

Find a polynomial-time algorithm for the largest edge set of maximum degree two that contains no four-cycle in an arbitrary graph.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000051 (AMR-029-0051), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Maximum square-free 2-matching. Original source indexed by AMR-029-0051. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Maximum square-free 2-matching. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Maximum_square-free_2-matching.