pipette
ESEspañol

Triangle-overlap cores and density bounds for Tuza's conjecture

Yasuhito Tsujimura

Preprint

In the authors' words

For a finite simple graph , let be the maximum number of edge-disjoint triangles and let be the minimum number of edges meeting every triangle. We prove when each edge belongs to at most four triangles, the edges belonging to four triangles form components with at most two edges, and the maximum average degree is at most . No upper bound on maximum vertex degree is imposed. We also localize the density condition. Let be the Hifumi core, defined as the vertex set of the 4-core of the spanning subgraph formed by edges belonging to at least three triangles. It suffices to impose the density condition on , including all original edges between vertices of . More generally, when the four-triangle edges have maximum degree at most two, reductions produce a subgraph with . Consequently an empty core gives a density-free sufficient condition. For the first graph class, a quantitative surplus argument strengthens both the global and localized density conditions to the strict bound . The proof combines edge reductions, discharging, finite certificates and a weak K\"onig--Egerv\'ary lemma for links of arbitrary order. The general conjecture and the removal of the density condition from the first graph class remain unresolved here.

Main resultLimitation the authors admit

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 21 pages, 3 figures. Verification materials: reserved DOI 10.5281/zenodo.24047493; public release planned after arXiv announcement