PreprintCC BY-NC-SA 4.0arXiv
Tuza's Conjecture for Graphs of Maximum Degree at Most 10
Abstract
For a finite simple graph G, let ν(G) be the maximum number of pairwise edge disjoint triangles and τ(G) the minimum number of edges meeting every triangle. Tuza conjectured in 1981 that every such G satisfies τ(G) ≤ 2 ν(G). We prove the conjecture for the class of graphs with Δ≤10.
Related
- e-Positive caterpillars have maximum degree at most three
- Strong edge coloring of graphs with maximum degree $6$
- Degree sequences of spectrally extremal connected nonregular graphs with prescribed maximum degree: the dense case
- Extremal spectral radius of nonregular graphs with a fixed odd maximum degree
- Treedepth is NP-Hard on Planar Graphs of Maximum Degree 3
BibTeX
@misc{kandasamy2026tuzas,
title = {{Tuza's Conjecture for Graphs of Maximum Degree at Most 10}},
author = {Amrit Kandasamy},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15269},
eprint = {2610.15269},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15269},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Tuza's Conjecture for Graphs of Maximum Degree at Most 10
AU - Amrit Kandasamy
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15269
UR - https://arxiv.org/abs/2610.15269
AB - For a finite simple graph G, let ν(G) be the maximum number of pairwise edge disjoint triangles and τ(G) the minimum number of edges meeting every triangle. Tuza conjectured in 1981 that every such G satisfies τ(G) ≤ 2 ν(G). We prove the conjecture for the class of graphs with Δ≤10.
ER -