Abstract
An identifying code of a closed-twin-free graph (Formula presented.) is a set (Formula presented.) of vertices of (Formula presented.) such that any two vertices in (Formula presented.) have a distinct, nonempty intersection between their closed neighborhood and (Formula presented.). It was conjectured that there exists a constant (Formula presented.) such that for every connected closed-twin-free graph (Formula presented.) of order (Formula presented.) and maximum degree (Formula presented.), the graph (Formula presented.) admits an identifying code of size at most (Formula presented.). In [D. Chakraborty, F. Foucaud, M. A. Henning, and T. Lehtilä. Identifying codes in graphs of given maximum degree: Characterizing trees. Discrete Mathematics 349(2), 114826, 2026], we proved the conjecture for all trees. In this article, we show that the conjecture holds for all triangle-free graphs, with the same list of exceptional graphs needing (Formula presented.) as for trees: for (Formula presented.) suffices and there is only a set of 12 trees requiring (Formula presented.) for (Formula presented.), and when (Formula presented.) this set is reduced to the (Formula presented.) -star only. Our proof is by induction, whose starting point is the above result for trees. Along the way, we prove a generalized version of Bondy’s theorem on induced subsets [J. A. Bondy. Induced subsets. Journal of Combinatorial Theory, Series B, 1972] that we use as a tool in our proofs. We also use our main result for triangle-free graphs to prove the upper bound (Formula presented.) for graphs that can be made triangle-free by the removal of (Formula presented.) edges.