---

Claim. Theorem 2(a) of Zs. Tuza, Covering all cliques of a graph, Discrete Math. 86 (1990), no. 1--3, 117--126 (issue of December 1990, the claim's date; received 28 August 1986), p. 119: "Let $G$ be a chordal graph on $n$ vertices. Then $\tau_C(G) \leq n/2$, and equality holds if and only if $G$ contains a perfect matching $E_M$ such that every $e_i \in E_M$ is a cut-edge of $G$." Here $\tau_C(G)$ is the least number of vertices meeting every maximal clique on at least two vertices, the $\tau(G)$ of Problem 151. Since $\tau(G)$ is an integer, $\tau(G)\le\lfloor n/2\rfloor$. The complete bipartite graph $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ is triangle-free with independence number $\lceil n/2\rceil$, so $H(n)\le\lceil n/2\rceil$ for $n\ge2$, and every chordal graph on $n$ vertices satisfies $\tau(G)\le\lfloor n/2\rfloor=n-\lceil n/2\rceil\le n-H(n)$ (for $n=1$ both sides are $0$).

The bound itself is older. Tuza credits the case to Aigner and Andreae (a manuscript of 1986, which he cites as unpublished) and gives his own short proof through a perfect elimination order. Erdős, Gallai and Tuza (Discrete Math. 108 (1992), p. 281) record that chordal graphs have the $\langle2\rangle$-property, $\tau_C(G)\le|V(G)|/2$, citing the same manuscript and Tuza's paper, and Erdős (Discrete Math. 72 (1988), p. 82) reports Gallai's conjecture that the cliques of a chordal graph on $n$ vertices can be met by $[n/2]$ vertices as "indeed proved by Aigner, Andreae and Tuza". Tuza's paper is the first publication of a proof, and its card is Tuza 1990.

Covers. The inequality $\tau(G)\le n-H(n)$ for every chordal graph, of any order. Graphs that are not chordal are not addressed.

Depends on. No page of this wiki; the step from $n/2$ to $n-H(n)$ is the one line above.

Acceptance. Refereed: the paper is a publication in Discrete Mathematics, and it thanks the referee. The site does not mention the chordal case, so no curator credit applies.