Induced paths in graphs without anticomplete cycles

DOI10.1016/J.JCTB.2023.10.003MaRDI QIDQ6144401zbMATH OpenFDO

Authors

Publication date 29 January 2024

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2212.01089

zbMATH Keywords

induced subgraphsLe's conjecture

Mathematics Subject Classification ID

Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: Let us say a graph is $smathcalO$-free, where $sge1$ 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 $2mathcalO$-free in polynomial time; and there was an open conjecture, due to Ngoc Khang Le, that $2mathcalO$-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 $sge1$, there exists $c>0$ such that every $smathcalO$-free graph $G$ has at most $|G{|}^c$ induced paths. This provides a poly-time algorithm to test if a graph is $smathcalO$-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'epr'es, Esperet, Geniet, Hilaire, Thomass'e and Wesolek, that in every $smathcalO$-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.

Recommendations

• Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
• Few induced disjoint paths for \(H\)-free graphs
• Few induced disjoint paths for \(H\)-free graphs
• Colouring square-free graphs without long induced paths
• Some results on graphs without long induced paths

Cites work

• Complexity of independent set reconfigurability problems
• On Independent Circuits Contained in a Graph

Cited in

(2)

• Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
• Induced disjoint paths without an induced minor

This page was built for publication: Induced paths in graphs without anticomplete cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6144401)