Induced paths in graphs without anticomplete cycles

TY - JOUR

T1 - Induced paths in graphs without anticomplete cycles

AU - Nguyen, Tung

AU - Scott, Alex

AU - Seymour, Paul

N1 - Publisher Copyright: © 2023 The Author(s)

PY - 2024/1

Y1 - 2024/1

N2 - 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.

AB - 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.

KW - Induced subgraphs

UR - http://www.scopus.com/inward/record.url?scp=85174405938&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85174405938&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2023.10.003

DO - 10.1016/j.jctb.2023.10.003

M3 - Article

SN - 0095-8956

VL - 164

SP - 321

EP - 339

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -