Pith. sign in

REVIEW 1 major objections 4 minor 7 references

An improved upper bound for Tuza's conjecture via 2-colorable triangle families

T0 review · 1 major / 4 minor · reviewed 2026-08-28 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves tau(G) <= (63/22) nu(G), a new general upper bound for Tuza's conjecture, using a new lemma for 2-colorable triangle families.

desk verdict A small, genuine improvement to the best known bound for Tuza's conjecture, with a clean proof and one structural claim to check. read the letter →

arxiv 2608.23010 v1 pith:DKE3X4AT submitted 2026-08-24 math.CO

Lixing Yi This is my paper · ORCID
classification math.CO
keywords mathcaltriangleboundcolorableconjecturefracsizetriangles
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Tuza's conjecture asks whether you can always destroy all triangles in a graph by deleting at most twice as many edges as the maximum number of edge-disjoint triangles you can find. This is open for 40 years. The trivial guarantee is 3 times; the previous record was about 2.87 (66/23). This paper lowers it to about 2.86 (63/22).

The new tool is a structural observation. Call a collection of triangles "2-colorable" if you can paint the edges red and blue so that every triangle in the collection has exactly one red edge and two blue edges. The author proves that for such a family, you can always hit every triangle with at most (1+sqrt(3)) ~ 2.732 times the number of edge-disjoint triangles in the family. The proof combines two covering strategies: one that uses all edges of a maximum packing except some red edges, and one that uses the blue edges plus a cover of the remaining red-edge-only triangles. An induction trades off these two bounds to get the constant.

The author then observes that the leftover triangle family in Haxell's 1999 proof is exactly such a 2-colorable family, so the new lemma applies inside the old machinery. This yields the improved general bound. The paper also notes that a further improvement of the 2-colorable lemma to the conjectured factor 2 would push the general bound to 54/19.

Extended reading notes

Core claim

The central result is Theorem 1: for a 2-colorable triangle family F, tau(F) <= (1+sqrt(3)) nu(F). The paper then uses this to prove Corollary 1: for any graph G, tau(G) <= (63/22) nu(G), improving Haxell's 66/23. The abstract states: 'we prove tau(G) <= 63/22 nu(G), improving the previous bound tau(G) <= 66/23 nu(G) established by Haxell in 1999.'

Load-bearing premise

The proof of Corollary 1 depends on the claim in Section 3 that in Haxell's proof of Lemma 3.4 a triangle transversal of G is obtained by first adding E(B_1) union (E(B') cap E(B)), and that the uncovered triangles are precisely the family S of type (B',1) triangles sharing one edge with E(B')\E(B). If Haxell's construction adds different edges or leaves a different uncovered family, the improved bound on tau(S) would not transfer to G. This is an external precondition quoted from [3] and not reproduced in the paper.

Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

  1. Claim #1: The central result is Theorem 1: for a 2-colorable triangle family F, tau(F) <= (1+sqrt(3)) nu(F). The paper then uses this to prove Corollary 1: for any graph G, tau(G) <= (63/22) nu(G), improving Haxell's 66/23. The abstract states: 'we prove tau(G) <= 63/22 nu(G), improving the previous bound tau(G) <= 66/23 nu(G) established by Haxell in 1999.'

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper proves a new upper bound for Tuza's conjecture on triangle transversals. The main contribution is Theorem 1: for a 2-colorable triangle family F (one in which each triangle has two blue edges and one red edge), τ(F) ≤ (1+√3)ν(F). The proof is by induction using two lemmas: Lemma 2.1 gives τ(F) ≤ 3ν(F)−|B1|, and Lemma 2.2 gives τ(F) ≤ 2ν(F)+τ(F_R). Combining these yields the claimed constant. The paper then applies this result to improve the general bound for Tuza's conjecture, obtaining τ(G) ≤ 63/22ν(G) for every graph G, improving Haxell's bound of 66/23. A slightly sharper irrational bound (162+4√3)/59 is also stated.

Significance. If correct, the paper gives a genuine, though modest, improvement on a long-standing open problem: the best known general upper bound for Tuza's conjecture. The proof of Theorem 1 is self-contained and elegant, and the structural observation about 2-colorable triangle families is a useful new tool. The paper also correctly identifies that the constant 2 in Tuza's conjecture is best possible within this 2-colorable setting, since the four triangles of K4 are 2-colorable with τ=2ν=2. The application to the general bound is natural and the algebra in the weighted combination is sound. The small constant improvement from 66/23≈2.8696 to 63/22≈2.8636 is meaningful in a context where any progress is significant.

major comments (1)
  1. [Section 3, proof of Corollary 1] The proof of Corollary 1 relies on the assertion that in Haxell's proof of Lemma 3.4, a triangle transversal of G is obtained by first adding E(B1)∪(E(B')∩E(B)), that the size of this initial set is at most 3ν(G)−|B2|, and that the uncovered triangles are precisely S. These claims are not proved in the manuscript and are not part of the restated Lemma 3.4. They are load-bearing because the entire improvement depends on replacing Haxell's use of E(B'_1) as a transversal of S with the better bound τ(S)≤11/4|B'_1|. If Haxell's construction leaves a different family uncovered, or if the initial set has a different size, the improved bound would not transfer. The author should either reproduce the relevant part of Haxell's proof or provide a self-contained verification of these two specific facts.
minor comments (4)
  1. [Title] The title contains a typo: 'TRIANGLE F AMILIES' should read 'TRIANGLE FAMILIES'.
  2. [Section 3, definition of S] The definition of S as 'the family of type (B′,1) triangles that share exactly one edge with E(B′)\E(B)' is grammatically ambiguous. It should be clarified that S consists of type (B′,1) triangles whose unique edge in E(B′) lies in E(B′)\E(B).
  3. [Introduction] The term '2-colorable' may mislead readers who are accustomed to standard proper 2-coloring; I suggest using a different term or explicitly stating that the coloring is an arbitrary red/blue edge-coloring with the specified property, not necessarily proper.
  4. [Section 3, sharper bound] The statement that directly applying the constant 1+√3 yields the bound τ(G)≤(162+4√3)/59 is given without derivation. A short calculation showing the weighted combination with the optimal weights would help the reader verify the algebra.
Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claim rests on standard combinatorial facts and on four lemmas quoted from Haxell's 1999 paper. No free parameters are fitted to data, and no new entities are postulated. The main external assumption is the accuracy of Haxell's construction in Lemma 3.4.

assumptions (3)
  • domain assumption Haxell's Lemmas 3.1-3.4 (reference [3])
    The paper restates these four lemmas without proof and uses them in the combination that yields Corollary 1. If any of these lemmas is false or misquoted, the new general bound would not follow.
  • standard math Maximum independent family B intersects every triangle in F
    Used implicitly in the proof of Lemma 2.1 to assert that every triangle P must intersect E(B). This follows from maximality of a maximum packing.
  • standard math Local structure of two triangles sharing an edge: any triangle intersecting both must contain the shared edge or the fifth edge of the K4 minus an edge
    Used in Lemma 2.1's diamond argument; it is a standard finite fact about K4 minus an edge.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An improved upper bound for Tuza's conjecture via 2-colorable triangle families." pith.science (2026). https://pith.science/paper/DKE3X4AT

@misc{pith2026260823010,
  author       = {Pith},
  title        = {Pith review of: An improved upper bound for Tuza's conjecture via 2-colorable triangle families},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DKE3X4AT}},
  note         = {Machine review of arXiv:2608.23010}
}
abstract

Tuza's conjecture states that for any graph $G$, the minimum size of a triangle transversal $\tau(G)$ is at most twice the maximum size of a set of edge-disjoint triangles $\nu(G)$. In this note, we prove $\tau(G) \leq \frac{63}{22}\nu(G)$, improving the previous bound $\tau(G) \leq \frac{66}{23}\nu(G)$ established by Haxell in 1999. The key observation is that for a "2-colorable" family of triangles $\mathcal{F}$, where each triangle has two blue edges and one red edge, we can obtain $\tau(\mathcal{F})\leq (1+\sqrt{3})\nu(\mathcal{F})$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

  1. [1]

    Small Edge Sets Meeting all Triangles of a Graph , volume =

    Lakshmanan, Aparna and Bujtás, Csilla and Tuza, Zs , year =. Small Edge Sets Meeting all Triangles of a Graph , volume =. Graphs and Combinatorics , doi =

    work page

  2. [2]

    , year =

    Tuza, Z. , year =. A conjecture on triangles of graphs. , volume =. Graphs and Combinatorics , doi =

    work page

  3. [3]

    2021 , issn =

    On Tuza’s conjecture for triangulations and graphs with small treewidth , journal =. 2021 , issn =. doi:https://doi.org/10.1016/j.disc.2020.112281 , author =

    work page arXiv 2021

  4. [4]

    Tuza’s Conjecture for Threshold Graphs , volume=

    Bonamy, Marthe and Bożyk, Łukasz and Grzesik, Andrzej and Hatzel, Meike and Masařík, Tomáš and Novotná, Jana and Okrasa, Karolina , year=. Tuza’s Conjecture for Threshold Graphs , volume=. Discrete Mathematics & Theoretical Computer Science , publisher=. doi:10.46298/dmtcs.7660 , number=

    work page doi:10.46298/dmtcs.7660

  5. [5]

    Ryser's Conjecture for Tripartite 3-Graphs , volume =

    Aharoni, Ron , year =. Ryser's Conjecture for Tripartite 3-Graphs , volume =. Combinatorica , doi =

    work page

  6. [6]

    1999 , issn =

    Packing and covering triangles in graphs , journal =. 1999 , issn =. doi:https://doi.org/10.1016/S0012-365X(98)00183-6 , author =

    work page doi:10.1016/s0012-365x(98)00183-6 1999

  7. [7]

    , year =

    Tuza, Z. , year =. Conjecture. , journal =

    work page

Pith tools

Reviewed August 28, 2026 · model on record in the stance chip above.