Sparse Sets in Triangle-free Graphs
<|reference_start|>Sparse Sets in Triangle-free Graphs: 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.<|reference_end|>
@article{ekim2024sparse,
    title={Sparse Sets in Triangle-free Graphs},
    author={T{i}naz Ekim, Burak Nur Erdem, John Gimbel},
    journal={arXiv preprint arXiv:2406.03290},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.03290},
    primaryClass={math.CO cs.DM}
}