Back to Search
Start Over
Induced paths in graphs without anticomplete cycles.
- Source :
-
Journal of Combinatorial Theory - Series B . Jan2024, Vol. 164, p321-339. 19p. - Publication Year :
- 2024
-
Abstract
- Let us say a graph is O s -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 O 2 -free in polynomial time; and there was an open conjecture, due to Ngoc Khang Le, that O 2 -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 O s -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 O s -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 O s -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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *POLYNOMIAL time algorithms
*PATHS & cycles in graph theory
*GRAPH labelings
Subjects
Details
- Language :
- English
- ISSN :
- 00958956
- Volume :
- 164
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series B
- Publication Type :
- Academic Journal
- Accession number :
- 173890018
- Full Text :
- https://doi.org/10.1016/j.jctb.2023.10.003