Geodesic
Restriction on minimum degree in the contractible sets problem
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XIII, Tome 518 (2022), pp. 114-123 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Let $G$ be a $3$-connected graph. A set $W \subset V(G)$ is contractible if $G(W)$ is connected and $G - W$ is a $2$-connected graph. In 1994, McCuaig and Ota formulated the conjecture that, for any $k \in \mathbb{N}$, there exists $m \in \mathbb{N}$ such that any $3$-connected graph $G$ with $v(G) \geqslant m$ has a $k$-vertex contractible set. In this paper we prove that, for any $k \geqslant 5$, the assertion of the conjecture holds if $\delta(G) \geqslant \left[ \frac{2k + 1}{3} \right] + 2$. 
@article{ZNSL_2022_518_a2,
     author = {N. A. Karol},
     title = {Restriction on minimum degree in the contractible sets problem},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {114--123},
     year = {2022},
     volume = {518},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2022_518_a2/}
}
TY  - JOUR
AU  - N. A. Karol
TI  - Restriction on minimum degree in the contractible sets problem
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2022
SP  - 114
EP  - 123
VL  - 518
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2022_518_a2/
LA  - en
ID  - ZNSL_2022_518_a2
ER  - 
%0 Journal Article
%A N. A. Karol
%T Restriction on minimum degree in the contractible sets problem
%J Zapiski Nauchnykh Seminarov POMI
%D 2022
%P 114-123
%V 518
%U http://geodesic.mathdoc.fr/item/ZNSL_2022_518_a2/
%G en
%F ZNSL_2022_518_a2
N. A. Karol. Restriction on minimum degree in the contractible sets problem. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XIII, Tome 518 (2022), pp. 114-123. http://geodesic.mathdoc.fr/item/ZNSL_2022_518_a2/

[1] N. Karol, Contractible 6-vertex sets, manuscript

[2] D. V. Karpov, “Large contractible subgraphs of a $3$-connected graph”, Discussiones Mathematicae Graph Theory, 41 (2021), 83–101 | DOI

[3] D. V. Karpov, “Minimal biconnected graphs”, J. Math. Sci., 204 (2015), 244–257

[4] M. Kriesell, “Contractible subgraphs in $3$-connected graphs”, J. Comb. Theory Ser. B, 80 (2000), 32–48

[5] W. Mader, “High connectivity keeping sets in $n$-connected graphs”, Combinatorica, 24:3 (2004), 441–458

[6] W. Mader, “On vertices of degree $n$ in minimally $n$-connected graphs and digraphs”, Combinatorics, Paul Erdös is Eighty, 2 (1996), 423–449

[7] W. McCuaig, K. Ota, “Contractible triples in $3$-connected graphs”, J. Comb. Theory Ser. B, 60 (1994), 308–314

[8] W. T. Tutte, “A theory of $3$-connected graphs”, Konik. Nederl. Akad. van Wet., Proc., 64 (1961), 441–455

[9] N. Y. Vlasova, “Every $3$-connected graph on at least $13$ vertices has a contractible set on $5$ vertices”, Zap. Nauchn. Semin. POMI, 518, 2022, 5–93