Triangle Restoration and Packing–Covering Stability in Tuza's Conjecture

For a finite simple graph G, let ν(G) be the maximum number of edge-disjoint triangles and τ (G) the minimum size of a triangle edge cover. We integrate triangle-restoration criteria and packing–covering stability results. Restoring one triangle to a remainder with tripartite full triangle hypergraph preserves Tuza’s inequality; consequently the inequality holds for odd-cycle transversal at most four and, by an adaptation of Liu–Zeng, for sufficiently large graphs with e(G) ≥ n2/4− cn for every fixed c < 5/2. For two restored triangles we give complete proofs for exact-equality and essential-edge tripartite remainders, flat remainders, three specified nonflat star cores, and exact two-apex bowties with shared apices or mixed triangles. We prove closed- boundary deletion and stability criteria and a compression preserving four exact optimization values. Selected deductions are conditionally checked in Lean with their external mathematical inputs explicit; the remaining results have audited ordinary proofs. Unrestricted two-triangle restoration, OCT-five, and the fixed-c < 3 density extension remain unproved.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-10-29
DOI
https://doi.org/10.5281/zenodo.23774235
Primary Topic
Limits and Structures in Graph Theory
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Triangle Restoration and Packing–Covering Stability in Tuza's Conjecture

GPT Chat
2 links
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
article

Triangle Restoration and Packing–Covering Stability in Tuza's Conjecture

GPT Chat
article en

Abstract

For a finite simple graph G, let ν(G) be the maximum number of edge-disjoint triangles and τ (G) the minimum size of a triangle edge cover. We integrate triangle-restoration criteria and packing–covering stability results. Restoring one triangle to a remainder with tripartite full triangle hypergraph preserves Tuza’s inequality; consequently the inequality holds for odd-cycle transversal at most four and, by an adaptation of Liu–Zeng, for sufficiently large graphs with e(G) ≥ n2/4− cn for every fixed c < 5/2. For two restored triangles we give complete proofs for exact-equality and essential-edge tripartite remainders, flat remainders, three specified nonflat star cores, and exact two-apex bowties with shared apices or mixed triangles. We prove closed- boundary deletion and stability criteria and a compression preserving four exact optimization values. Selected deductions are conditionally checked in Lean with their external mathematical inputs explicit; the remaining results have audited ordinary proofs. Unrestricted two-triangle restoration, OCT-five, and the fixed-c < 3 density extension remain unproved.

Zenodo (CERN European Organization for Nuclear Research)
Openalex Percentile: Top 5%
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon