Haxell 1999 packing covering triangles graphs

../

lemma_1: The first of the four transversal bounds that combine into Haxell's Theorem 5: τ(G) ≤ (3 - γ)ν(G), where γν(G) is the largest number of edge-disjoint triangles each meeting a fixed maximum packing in exactly one edge.

lemma_2: The second of the four transversal bounds that combine into Haxell's Theorem 5: τ(G) ≤ (3/2 + 5γ/2 + 2β)ν(G), with γ and β the relative sizes of largest independent families of type-(B,1) and type-(B,2) triangles.

lemma_3: The third of the four transversal bounds that combine into Haxell's Theorem 5: τ(G) ≤ (3 - δ)ν(G), with δν(G) the size of a largest independent family of triangles that share exactly one edge with the auxiliary packing B', that edge lying outside E[B].

lemma_4: The fourth of the four transversal bounds that combine into Haxell's Theorem 5: τ(G) ≤ (3 + 3δ - β)ν(G); the lemma whose 3δ term the closing remark and the 2026 preprint of Yi each propose to sharpen.

theorem_5: Haxell's theorem that every graph G satisfies τ(G) ≤ (3 - ε)ν(G) with ε ≥ 3/23, that is τ(G) ≤ (66/23)ν(G), the refereed general bound toward Tuza's conjecture that Problem 167 records, with the closing remark on the improvement to ε = (23 - sqrt(481))/8.

---

P. E. Haxell, Packing and covering triangles in graphs, Discrete Mathematics 195 (1999), no. 1--3, 251--254, DOI 10.1016/S0012-365X(98)00183-6 (the printed first page carries the PII line "S0012-365X(98)00183-6" and no DOI); a Note, received 30 April 1997, revised 17 April 1998, accepted 4 May 1998; the author at the Department of Combinatorics and Optimization, University of Waterloo, partially supported by NSERC (footnote, p. 251). Cited as [Ha99] on the problem page. Its five references (p. 254) are Füredi, Matchings and covers in hypergraphs, Graphs Combin. 4 (1988), 115--206; Haxell and Kohayakawa, Packing and covering triangles in tripartite graphs, Graphs Combin. 14 (1998), 1--10; Krivelevich, On a conjecture of Tuza about packing and covering of triangles, Discrete Math. 142 (1995), 281--286; Tuza, Conjecture, Finite and Infinite Sets, Eger, Hungary 1981, Proc. Colloq. Math. Soc. J. Bolyai 37, North-Holland, Amsterdam, 1984, p. 888; and Tuza, A conjecture on triangles of graphs, Graphs Combin. 6 (1990), 373. None of the five is held.

The copy read for this card is the publisher's version of record: 4 pages, printed pp. 251--254 = PDF pp. 1--4 (printed p. $n$ is PDF p. $n-250$), a scan of the printed article (its metadata names an Acrobat 3.0 Capture plug-in and a January 2003 creation date) with an OCR text layer that locates passages and garbles the mathematics (the script letters $\mathscr B$, $\mathscr F$ and $\mathscr S$, the Greek letters $\nu$ and $\tau$, primes, subscripts and inequality signs come out as stray characters, and the displayed sum of the proof of Theorem 5 is unreadable in the text layer). No preprint or later version is known here. The version of record is available free of charge from the publisher's open archive, the DOI https://doi.org/10.1016/S0012-365X(98)00183-6 resolving to the article's PDF on ScienceDirect (PII S0012365X98001836), 208,323 bytes; it was read there. It prints "© 1999 Elsevier Science B.V. All rights reserved". The open archive's terms are the Elsevier user license https://www.elsevier.com/open-access/userlicense/1.0/, which the Crossref record names for the version of record (both read 2026-10-07): they allow non-commercial access, copying, translation and text and data mining, but not redistribution, display or adaptation; every other right is reserved.

Read status: claims checked for the abstract, the definitions of an independent family, a transversal, $\nu(G)$ and $\tau(G)$, the trivial bounds, the $K_4$ and $K_5$ examples and Tuza's conjecture (p. 251), the summary of the result (p. 252), the definitions of the types $(\mathscr B,i)$ and the families $\mathscr B_1$, $\mathscr B_2$, $\mathscr B'$, $\mathscr S$ and $\mathscr B_1'$ with their parameters $\gamma$, $\beta$ and $\delta$ (pp. 252--253), Lemmas 1--4 (pp. 252--253), Theorem 5 and the closing remark (p. 254), each read clause by clause on the page images of PDF pp. 1--4 on 2026-09-22. The proofs of Lemmas 1--4 and the displayed combination proving Theorem 5 (pp. 252--254) were read in full on the page images and each step was followed; the arithmetic of the combination was recomputed. The reference list (p. 254) was read on the page image. Nothing here is independently reviewed.

Contents

• Abstract and § 0, Introduction (pp. 251--252, page images). The abstract states the result in this form: when $\nu(G)$ is the largest size of a set of pairwise edge-disjoint triangles in $G$, some set $C$ of at most $(3-\varepsilon)\nu(G)$ edges meets every triangle of $G$ ($E(T)\cap C\ne\emptyset$ for every triangle $T$), with $\varepsilon>\frac3{23}$; its last sentence (quoted): "This is the first nontrivial bound known for a long-standing conjecture of Tuza." The introduction calls a family $\mathscr F$ of triangles independent when no two of its triangles share an edge, and a set $C\subset E(G)$ a transversal for $G$ when each triangle of $G$ has an edge in $C$; $\nu(G)$ is the largest size of an independent family and $\tau(G)$ the smallest size of a transversal. It then records the trivial bounds $\nu(G)\le\tau(G)\le3\nu(G)$, the examples $K^4$ and $K^5$ with $\tau(G)=2\nu(G)$, and Tuza's conjecture of 1981 [4] that $\tau(G)\le2\nu(G)$ for every graph $G$. The partial results recalled (pp. 251--252): Tuza [5] for planar graphs, for $K_5$-free chordal graphs and for graphs on $n$ vertices with $7n^2/16$ or more edges; Krivelevich [3] for graphs without homeomorphic copies of $K_{3,3}$, a paper that also considers two fractional versions of the conjecture; Tuza [5], $\tau(G)\le7\nu(G)/3$ for tripartite $G$, improved in [2] to $(2-\varepsilon)\nu(G)$ for a small positive $\varepsilon$. Then the statement of the result (p. 252, quoted): "In this note we show that for any graph $G$, we have $\tau(G)\le(3-\varepsilon)\nu(G)$, where $\varepsilon>3/23$."
• § 1, Proof of the main result (pp. 252--254, page images). Fix $G$ and a maximum independent family $\mathscr B$ of triangles, $|\mathscr B|=\nu$. A triangle is of type $(\mathscr B,i)$ if it has exactly $i$ edges in $E[\mathscr B]$, the edge set of the triangles of $\mathscr B$; every triangle has a type $i\in\{1,2,3\}$ by maximality. $\mathscr B_1$ is a maximum independent family of type-$(\mathscr B,1)$ triangles, $|\mathscr B_1|=\gamma\nu$. Lemma 1 (p. 252, quoted): "We have $\tau(G)\le(3-\gamma)\nu(G)$." Proof: each $T_1\in\mathscr B_1$ meets one $T_1'\in\mathscr B$; the set $\mathscr F$ of these has $|\mathscr F|= |\mathscr B_1|$ by maximality of $\mathscr B$; $E(T_1)\cup E(T_1')$ is a $K_4$ minus an edge; with $e(T_1)$ the shared edge and $e'(T_1)$ the missing edge when it lies in $G$, $C=E[\mathscr B\setminus\mathscr F]\cup {e(T)}\cup{e'(T)}$ has at most $(3-\gamma)\nu$ edges and is a transversal, since a triangle edge-disjoint from $\mathscr B\setminus\mathscr F$ must share an edge with both $T_1$ and $T_1'$ for some $T_1$, hence contain $e(T_1)$ or $e'(T_1)$. $G'$ is $G$ minus the edges of the triangles of $\mathscr B_1$, with $\nu(G')=\nu(1-\gamma)$ and only types $(\mathscr B,2)$ and $(\mathscr B,3)$ left; $\mathscr B_2$ is a maximum independent family of type-$(\mathscr B,2)$ triangles in $G'$, $|\mathscr B_2|=\beta\nu$. Lemma 2 (p. 252, quoted): "We have $\tau(G)\le(3/2+5\gamma/2+2\beta)\nu$." Proof: $C=E[\mathscr B_1]\cup E[\mathscr B_2]\cup C'$ with $C'$ a minimum set of edges whose removal makes the graph $H$ on $E[\mathscr B]\setminus(E[\mathscr B_1]\cup E[\mathscr B_2])$ bipartite, so $|C'|\le|E(H)|/2$; every remaining type-$(\mathscr B,3)$ triangle lies in $H$. $\mathscr B'$ is a maximum independent family in $G'$ subject to $|E[\mathscr B']\setminus E[\mathscr B]|\ge\beta\nu$ (it exists because of $\mathscr B_2$), $|\mathscr B'|\le\nu(1-\gamma)$; $\mathscr S$ is the set of triangles with exactly one edge in $E[\mathscr B']$, that edge in $E[\mathscr B']\setminus E[\mathscr B]$; $\mathscr B_1'$ is a maximum independent subset of $\mathscr S$, $|\mathscr B_1'|=\delta\nu$. Lemma 3 (p. 253, quoted): "We have $\tau(G)\le(3-\delta)\nu$." Proof: the Lemma 1 construction inside $G'$ with $\mathscr B'$ and $\mathscr B_1'$ gives a transversal $C'$ of $G'$ with $|C'|\le3|\mathscr B'|-\delta\nu$, using that the only edge of $T_1'$ in $E[\mathscr B']\setminus E[\mathscr B]$ is $e(T_1)$ (a second one would make $T_1'$ a type-$(\mathscr B,1)$ triangle, of which $G'$ has none); $C'\cup E[\mathscr B_1]$ is a transversal of $G$ of size at most $(3-\delta)\nu$. Lemma 4 (p. 253, quoted): "We have $\tau(G)\le(3+3\delta-\beta)\nu$." Proof (pp. 253--254): $C=E[\mathscr B_1]\cup E[\mathscr B_1']\cup(E[\mathscr B]\cap E[\mathscr B'])$; $\mathscr B'$ is maximal in $G'$, so $E[\mathscr B']$ is a transversal of $G'$, and a triangle of $G'$ disjoint from $E[\mathscr B']\cap E[\mathscr B]$ cannot contain two or three edges of $E[\mathscr B']\setminus E[\mathscr B]$, so it lies in $\mathscr S$ and contains an edge of $E[\mathscr B_1']$. Theorem 5 (p. 254, quoted): "We have $\tau(G)\le(3-\varepsilon)\nu$, where $\varepsilon\ge3/23$." Proof, the displayed combination of the four lemmas with weights $1$, $\frac25$, $\frac{12}5$ and $\frac45$: $\frac{23}5\tau(G)\le[(3-\gamma)+ (\frac35+\gamma+\frac45\beta)+(\frac{36}5-\frac{12}5\delta)+(\frac{12}5+ \frac{12}5\delta-\frac45\beta)]\nu(G)=\frac{66}5\nu(G)$, so $\tau(G)\le\frac{66}{23}\nu(G)$; recomputed here, the weights sum to $\frac{23}5$, the parameters cancel and the constants sum to $3+\frac{51}5=\frac{66}5$. Closing remark (p. 254, quoted): "The bound for $\varepsilon$ can be improved slightly to $(23-\sqrt{481})/8>3/23$ by using induction in Lemma 4 to replace the $3\delta$ bound by $(3-\varepsilon)\delta$." No proof of the remark is printed; $3-(23-\sqrt{481})/8=(1+\sqrt{481})/8=2.866\ldots$, against $\frac{66}{23}=2.869\ldots$. A filing observation, not a review verdict: the abstract and p. 252 state the result with the strict "$\varepsilon>3/23$", while Theorem 5 states "$\varepsilon\ge3/23$" and its printed proof gives exactly $\frac{66}{23}$; the strict form rests on the closing remark. The bound carries no error term: the theorem is $\tau(G)\le\frac{66}{23}\nu(G)$ for every graph $G$.
• References (p. 254, page image): five items, listed above.

Compiled scope

The paper is compiled at statement depth for the result the citing problem consumes, Theorem 5 (p. 254), read on the page image and paged on theorem_5, and for its four lemmas (pp. 252--253), which the card of the 2026 preprint of Yi consumes for its Corollary 1, paged on lemma_1, lemma_2, lemma_3 and lemma_4; the proof of Theorem 5 (Lemmas 1--4 and the displayed combination, pp. 252--254) was read in full on the page images and followed, with the arithmetic recomputed. The closing remark is recorded as an author's statement without a printed proof. Nothing here is independently reviewed.

Bears on. #167: Theorem 5 (printed p. 254, PDF p. 4), "We have $\tau(G)\le(3-\varepsilon)\nu$, where $\varepsilon\ge3/23$", that is $\tau(G)\le\frac{66}{23}\nu(G)$ for every graph $G$, is the refereed general bound toward Tuza's conjecture $\tau(G)\le2\nu(G)$; the site's commentary writes it as "$\le(3-\frac3{23}+o(1))k$", and the paper's bound carries no $o(1)$ term. Page 251 states the trivial bounds $\nu(G)\le\tau(G)\le3\nu(G)$, the tightness of $2$ for $K^4$ and $K^5$, and Tuza's 1981 conjecture with its Bolyai citation [4], the same entry as the page's [Tu81]. The closing remark (p. 254) is the improvement to $(1+\sqrt{481})/8$ that the 2026 preprint of Yi attributes to the paper "but the proof was omitted"; the paper prints the remark as one sentence that names the method, and no proof. The paper does not prove or disprove the conjecture and settles nothing the problem page leaves open. Lemmas 1--4 (lemma_1 to lemma_4, pp. 252--253) bear on the problem only as the four inequalities that Theorem 5 combines and that the 2026 preprint of Yi restates for its claimed, unrefereed constant $\frac{63}{22}$.

Results.

• Theorem 5 (p. 254): $\tau(G)\le(3-\varepsilon)\nu(G)$ with $\varepsilon\ge3/23$, that is $\tau(G)\le\frac{66}{23}\nu(G)$, for every graph $G$; with the closing remark on $(23-\sqrt{481})/8$.
• Lemma 1 (p. 252): $\tau(G)\le(3-\gamma)\nu(G)$, with $\gamma\nu$ the size of a largest independent family of type-$(\mathscr B,1)$ triangles.
• Lemma 2 (p. 252, proof pp. 252--253): $\tau(G)\le(3/2+5\gamma/2+2\beta)\nu$.
• Lemma 3 (p. 253): $\tau(G)\le(3-\delta)\nu$.
• Lemma 4 (p. 253, proof pp. 253--254): $\tau(G)\le(3+3\delta-\beta)\nu$, the lemma whose $3\delta$ term the closing remark proposes to sharpen.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.