Constructing extremal triangle-free graphs using integer programming
Ali Erdem Banak, Tınaz Ekim, Z. Caner Taşkın · arXiv (Cornell University) · 2023
The maximum number of edges in a graph with matching number m and maximum degree d has been determined in [1] and [2], where some extremal graphs have also been provided. Then, a new question has emerged: how the maximum edge count is affected by forbidding some subgraphs occurring in these extremal graphs? In [3], the problem is solved in triangle-free graphs for $d \geq m$, and for $d d$. Our results endorse the formula for the number of edges in all extremal triangle-free graphs conjectured in [3].