Sparse graphs with bounded induced cycle packing number have logarithmic treewidth

DOI10.1016/J.JCTB.2024.03.003MaRDI QIDQ6500104

Louis Esperet, Marthe Bonamy, Colin Geniet, Steéphan Thomassé, Édouard Bonnet, Alexandra Wesolek, Hugues Déprés, Claire Hilaire

Publication date: 10 May 2024

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

zbMATH Keywords

treewidthinduced cycles

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Paths and cycles (05C38)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• Induced packing of odd cycles in planar graphs
• Dominating sets for split and bipartite graphs
• Clustering and domination in perfect graphs
• Graph minors. V. Excluding a planar graph
• Mangoes and blueberries
• Which problems have strongly exponential complexity?
• Induced subdivisions and bounded expansion
• Algorithmic graph theory and perfect graphs
• Graph minors. XIII: The disjoint paths problem
• Treewidth versus clique number in graph classes with a forbidden structure
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Grid induced minor theorem for graphs of small degree
• Solving the stable set problem in terms of the odd cycle packing number
• Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
• A strongly polynomial algorithm for bimodular integer linear programming
• EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
• Twin-width I: Tractable FO Model Checking
• The stable set problem in graphs with bounded genus and bounded odd cycle packing number
• On Independent Circuits Contained in a Graph
• Parameterized Algorithms
• On a problem of K. Zarankiewicz
• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
• Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time

This page was built for publication: Sparse graphs with bounded induced cycle packing number have logarithmic treewidth