The maximum number of triangles in graphs without large linear forests

2018/12/21 by Xiuzhuan Duan, Jian Wang, Duan, Xiuzhuan +3
Computer Science · Mathematics · Neuroscience · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Nuclear Receptors and Signaling

paper · pdf · doi:10.48550/arxiv.1812.09089

openalex publication_date 2018/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G be a graph on n vertices. A linear forest is a graph consisting of vertex-disjoint paths and isolated vertices. A maximum linear forest of G is a subgraph of G with maximum number of edges, which is a linear forest. We denote by l(G) this maximum number. Let t=\lfloor (k-1)/2 \rfloor. Recently, Ning and Wang \citeboning proved that if l(G)=k-1, then for any k

Related

• A lower bound on the order of the largest induced linear forest in triangle-free planar graphs
• New bounds for linear arboricity and related problems
• A better bound on the largest induced forests in triangle-free planar graphs
• Towards the linear arboricity conjecture
• New results on large induced forests in graphs