A1 Refereed original research article in a scientific journal
Identifying Codes in Triangle‐Free Graphs of Bounded Maximum Degree
Authors: Chakraborty, Dipayan; Foucaud, Florent; Henning, Michael A.; Lehtilä, Tuomo
Publisher: Wiley
Publication year: 2026
Journal: Journal of Graph Theory
Article number: jgt.70025
ISSN: 0364-9024
eISSN: 1097-0118
DOI: https://doi.org/10.1002/jgt.70025
Publication's open availability at the time of reporting: No Open Access
Publication channel's open availability : Partially Open Access publication channel
Web address : https://doi.org/10.1002/jgt.70025
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.
Funding information in the publication:
The first two authors were supported by the French government IDEX\u2010ISITE initiative CAP 20\u201025 (ANR\u201016\u2010IDEX\u20100001), the International Research Center \u201CInnovation Transportation and Production Systems\u201D of the I\u2010SITE CAP 20\u201025, and the ANR project GRALMECO (ANR\u201021\u2010CE48\u20100004). The research of Dipayan Chakraborty was supported in part by the Lebanese American University under the President's Intramural Research Fund PIRF0056. The research of Michael Henning was supported in part by the South African National Research Foundation (grant number 129265) and the University of Johannesburg. The Research of Tuomo Lehtil\u00E4 was partially supported by Business Finland project 10769/31/2022 6GTNF and Academy of Finland grants 338797 and 358718.
