Maximum size of a triangle-free graph with bounded maximum degree and matching number
Journal of Combinatorial Optimization, cilt.47, sa.4, 2024 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 47 Sayı: 4
- Basım Tarihi: 2024
- Doi Numarası: 10.1007/s10878-024-01123-z
- Dergi Adı: Journal of Combinatorial Optimization
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Anahtar Kelimeler: Extremal graphs, Triangle-free graphs, Erdos-Stone's Theorem, Turan's Theorem, Integer programming
- Boğaziçi Üniversitesi Adresli: Evet
Özet
Determining the maximum number of edges under degree and matching number constraints have been solved for general graphs in Chvátal and Hanson (J Combin Theory Ser B 20:128–138, 1976) and Balachandran and Khare (Discrete Math 309:4176–4180, 2009). It follows from the structure of those extremal graphs that deciding whether this maximum number decreases or not when restricted to claw-free graphs, to C4-free graphs or to triangle-free graphs are separately interesting research questions. The first two cases being already settled in Dibek et al. (Discrete Math 340:927–934, 2017) and Blair et al. (Latin American symposium on theoretical informatics, 2020), in this paper we focus on triangle-free graphs. We show that unlike most cases for claw-free graphs and C4-free graphs, forbidding triangles from extremal graphs causes a strict decrease in the number of edges and adds to the hardness of the problem. We provide a formula giving the maximum number of edges in a triangle-free graph with degree at most d and matching number at most m for all cases where d≥m, and for the cases where d