Let us say a graph is Os-free, where s≥1 is an integer, if there do not exist s cycles of the graph that are pairwise vertex-disjoint and have no edges joining them. The structure of such graphs, even when s=2, is not well understood. For instance, until now we did not know how to test whether a graph is O2-free in polynomial time; and there was an open conjecture, due to Ngoc Khang Le, that O2-free graphs have only a polynomial number of induced paths. In this paper we prove Le's conjecture; indeed, we will show that for all s≥1, there exists c>0 such that every Os-free graph G has at most |G|c induced paths, where |G| is the number of vertices. This provides a poly-time algorithm to test if a graph is Os-free, for all fixed s. The proof has three parts. First, there is a short and beautiful proof, due to Le, that reduces the question to proving the same thing for graphs with no cycles of length four. Second, there is a recent result of Bonamy, Bonnet, Déprés, Esperet, Geniet, Hilaire, Thomassé and Wesolek, that in every Os-free graph G with no cycle of length four, there is a set of vertices that intersects every cycle, with size logarithmic in |G|. And third, there is an argument that uses the result of Bonamy et al. to deduce the theorem. The last is the main content of this paper.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Induced subgraphs