EUVIMEDEUVIMED entdecken
Crossref

Unavoidable Induced Subgraphs of Large 2-Connected Graphs

Sarah Allred, Guoli Ding, Bogdan Oporowski

SIAM Journal on Discrete Mathematics · 30.06.2023 · 37 (2) · 684-698

DOI: 10.1137/21m1447593 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 31.05.2023. Verfasst von Sarah Allred und 2 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 10 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Ramsey proved that for every positive integer [Formula: see text], every sufficiently large graph contains an induced [Formula: see text] or [Formula: see text]. Among the many extensions of Ramsey’s theorem, there is an analogue for connected graphs: For every positive integer [Formula: see text], every sufficiently large connected graph contains an induced [Formula: see text], [Formula: see text], or [Formula: see text]. In this paper, we establish an analogue for 2-connected graphs. In particular, we prove that for every integer exceeding two, every sufficiently large 2-connected graph contains one of the following as an induced subgraph: [Formula: see text], a subdivision of [Formula: see text], a subdivision of [Formula: see text] with an edge between the two vertices of degree [Formula: see text], and a well-defined structure similar to a ladder.

Zitieren

APA

Allred, S., Ding, G., & Oporowski, B. (2023). Unavoidable Induced Subgraphs of Large 2-Connected Graphs. SIAM Journal on Discrete Mathematics, 37(2), 684-698. https://doi.org/10.1137/21m1447593

Vancouver

Allred S, Ding G, Oporowski B. Unavoidable Induced Subgraphs of Large 2-Connected Graphs. SIAM Journal on Discrete Mathematics. 2023;37(2):684-698. doi:10.1137/21m1447593

BibTeX
@article{Allred2023,
  author = {Allred, Sarah and Ding, Guoli and Oporowski, Bogdan},
  title = {Unavoidable Induced Subgraphs of Large 2-Connected Graphs},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2023},
  volume = {37},
  number = {2},
  pages = {684--698},
  doi = {10.1137/21m1447593}
}
Kostenlos starten →