Triangle-overlap cores and density bounds for Tuza's conjecture
En palabras de los autores
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.
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 21 pages, 3 figures. Verification materials: reserved DOI 10.5281/zenodo.24047493; public release planned after arXiv announcement