Identifying Codes in Triangle‐Free Graphs of Bounded Maximum Degree

ABSTRACT An identifying code of a closed‐twin‐free graph is a set of vertices of such that any two vertices in have a distinct, nonempty intersection between their closed neighborhood and . It was conjectured that there exists a constant such that for every connected closed‐twin‐free graph of order and maximum degree , the graph admits an identifying code of size at most . 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 as for trees: for suffices and there is only a set of 12 trees requiring for , and when this set is reduced to the ‐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 for graphs that can be made triangle‐free by the removal of edges.