Unavoidable Induced Subgraphs of Large 2-Connected Graphs
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.
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}
}
EUVIMED