Tuza's conjecture for graphs of maximum degree at most seven
Tuza conjectured that every finite simple graph $G$ satisfies $τ(G) \leq 2ν(G)$, where $ν(G)$ is the maximum number of pairwise edge-disjoint triangles and $τ(G)$ is the minimum number of edges whose deletion makes $G$ triangle-free. Puleo proved the conjecture for every graph of maximum average degree less than $7$; this covers maximum degree at most $6$ but no $7$-regular graph. We prove the conjecture for maximum degree at most $7$. The proof uses Puleo's reducible-set framework. At average degree seven his discharging step no longer forces a reducible configuration. In a minimal…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.06538
curl -X POST /api/v1/records/arxiv/2608.06538/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.06538/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'