More Web Proxy on the site http://driver.im/

research-article

Induced subgraphs and tree decompositions VII. Basic obstructions in H-free graphs

Authors:

Tara Abrishami,

Maria Chudnovsky,

Sophie SpirklAuthors Info & Claims

Volume 164, Issue C

Pages 443 - 472

https://doi.org/10.1016/j.jctb.2023.10.008

Published: 01 February 2024 Publication History

Abstract

We say a class C of graphs is clean if for every positive integer t there exists a positive integer w ( t ) such that every graph in C with treewidth more than w ( t ) contains an induced subgraph isomorphic to one of the following: the complete graph K t, the complete bipartite graph K t, t, a subdivision of the ( t × t )-wall or the line graph of a subdivision of the ( t × t )-wall. In this paper, we adapt a method due to Lozin and Razgon (building on earlier ideas of Weißauer) to prove that the class of all H-free graphs (that is, graphs with no induced subgraph isomorphic to a fixed graph H) is clean if and only if H is a forest whose components are subdivided stars.

Their method is readily applied to yield the above characterization. However, our main result is much stronger: for every forest H as above, we show that forbidding certain connected graphs containing H as an induced subgraph (rather than H itself) is enough to obtain a clean class of graphs. Along the proof of the latter strengthening, we build on a result of Davies and produce, for every positive integer η, a complete description of unavoidable connected induced subgraphs of a connected graph G containing η vertices from a suitably large given set of vertices in G. This is of independent interest, and will be used in subsequent papers in this series.

References

[1]

P. Aboulker, I. Adler, E.J. Kim, N.L.D. Sintiari, N. Trotignon, On the treewidth of even-hole-free graphs, Eur. J. Comb. 98 (2021).

[2]

Abrishami, T.; Chudnovsky, M.; Dibek, C.; Hajebi, S.; Rzążewski, P.; Spirkl, S.; Vušković, K. (2021): Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree. arXiv:2108.01162.

[3]

Abrishami, T.; Chudnovsky, M.; Hajebi, S.; Spirkl, S. (2022): Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs. arXiv:2203.06775.

[4]

Abrishami, T.; Alecu, B.; Chudnovsky, M.; Hajebi, S.; Spirkl, S. (2022): Induced subgraphs and tree decompositions V. One neighbor in a hole. arXiv:2205.04420.

[5]

M. Ajtai, J. Komlós, E. Szemerédi, A note on Ramsey numbers, J. Comb. Theory, Ser. A 29 (1980) 354–360.

[6]

B. Alecu, M. Chudnovsky, S. Hajebi, S. Spirkl, Induced subgraphs and tree decompositions XIII. Basic obstructions in H-free graphs for finite H, 2023, manuscript.

[7]

Bonamy, M.; Bonnet, É.; Déprés, H.; Esperet, L.; Geniet, C.; Hilaire, C.; Thomassé, S.; Wesolek, A. (2022): Sparse graphs with bounded induced cycle packing number have logarithmic treewidth. arXiv:2206.00594.

[8]

H. Bodlaender, A. Koster, Safe separators for treewidth, Discrete Math. 306 (3) (2006) 337–350.

[9]

H.L. Bodlaender Treewidth, Structure and algorithms, in: SIROCCO 2007: Proceedings of the 14th International Colloquium on Structural Information and Communication Complexity, 2007, pp. 11–25.

[10]

Davies, J. : appeared in an, Oberwolfach technical report https://doi.org/10.4171/OWR/2022/1.

[11]

Davies, J. (2020): Vertex-minor-closed classes are χ-bounded. arXiv:2008.05069.

[12]

J. Erde, D. Weißauer, A short derivation of the structure theorem for graphs with excluded topological minors, SIAM J. Discrete Math. 33 (3) (2019) 1654–1661.

[13]

P. Gartland, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, P. Rzążewski, Finding large induced sparse subgraphs in C > t-free graphs in quasipolynomial time, in: STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 330–341.

[14]

M. Grohe, D. Marx, Structure theorem and isomorphism test for graphs with excluded topological subgraphs, SIAM J. Comput. 44 (1) (2015) 114–159.

[15]

T. Korhonen, Grid induced minor theorem for graphs of small degree, J. Comb. Theory, Ser. B 160 (2023) 206–214.

[16]

V. Lozin, I. Razgon, Tree-width dichotomy, Eur. J. Comb. 103 (2022).

[17]

N. Robertson, P. Seymour, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms 7 (3) (1986) 309–322.

[18]

N. Robertson, P. Seymour, Graph minors. V. Excluding a planar graph, J. Comb. Theory, Ser. B 41 (1) (1986) 92–114.

Digital Library

[19]

N.L.D. Sintiari, N. Trotignon, (Theta, triangle)-free and (even-hole, K4)-free graphs. Part 1: layered wheels, J. Graph Theory 97 (4) (2021) 475–509.

[20]

D. Weißauer, In absence of long chordless cycles, large tree-width becomes a local phenomenon, J. Comb. Theory, Ser. B 139 (2019) 342–352.

[21]

D. Weißauer, On the block number of graphs, SIAM J. Discrete Math. 33 (2019) 346–357.

Index Terms

Induced subgraphs and tree decompositions VII. Basic obstructions in H-free graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Graph enumeration
2. Theory of computation

Index terms have been assigned to the content through auto-classification.

Recommendations

Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree
Abstract
This paper is motivated by the following question: what are the unavoidable induced subgraphs of graphs with large treewidth? Aboulker et al. made a conjecture which answers this question in graphs of bounded maximum degree, asserting that for ...
Odd Induced Subgraphs in Planar Graphs with Large Girth
Abstract
A long-standing conjecture asserts that there is a positive constant c such that every n-vertex graph without isolated vertices contains an induced subgraph with all degrees odd on at least cn vertices. Recently, Ferber and Krivelevich confirmed ... $^{}$ $^{}$ $^{}$ $_{}$
Forbidden set of induced subgraphs for 2-connected supereulerian graphs

Let H={H1,,Hk} be a set of connected graphs. A graph is said to be H-free if it does not contain any member of H as an induced subgraph. We show that if the following statements hold, |H|2,K1,3H,for any integer n0, every 2-connected H-free graph G of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Combinatorial Theory Series B

Journal of Combinatorial Theory Series B Volume 164, Issue C

Jan 2024

549 pages

Issue’s Table of Contents

Elsevier Inc.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 February 2024

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents