Received July 9, 2024. Published online June 10, 2025.
Abstract: A set of vertices is $k$-sparse if it induces a graph with a maximum degree of at most $k$. In this missive, we consider the order of the largest $k$-sparse set in a triangle-free graph of fixed order. We show, for example, that every triangle-free graph of order 11 contains a 1-sparse 5-set; every triangle-free graph of order 13 contains a 2-sparse 7-set; and every triangle-free graph of order 8 contains a 3-sparse 6-set. Further, these are all best possible. For fixed $k$, we consider the growth rate of the largest $k$-sparse set of a triangle-free graph of order $n$. Also, we consider Ramsey numbers of the following type. Given $i$, what is the smallest $n$ having the property that all triangle-free graphs of order $n$ contain a 4-cycle or a $k$-sparse set of order $i$. We use both direct proof techniques and an efficient graph enumeration algorithm to obtain several values for defective Ramsey numbers and a parameter related to largest sparse sets in triangle-free graphs, along with their extremal graphs.
Affiliations: Tınaz Ekim (corresponding author), Burak Nur Erdem, Department of Industrial Engineering, Boğaziçi University, 34342, Bebek, Istanbul, Turkey, e-mail: tinaz.ekim@bogazici.edu.tr, burak.erdem@bogazici.edu.tr; John Gimbel, Mathematics and Statistics, University of Alaska, 1731 South Chandalar Dr., Fairbanks, AK 99775-6660, USA, e-mail: jggimbel@alaska.edu
