Article in press
Authors:
Shuai Kou
Department of Mathematics，
Taiyuan University of Technology，
Taiyuan， Shanxi， 030024, China
email: koushuai828@163.com
Weihau Yang
Department of Mathematics, Taiyuan University of Technology, Shanxi Taiyuan-030024
email: ywh222@163.com
Title:
Contractible subgraphs of quasi 5-connected graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-09-20 , Revised: 2024-08-29 , Accepted: 2024-08-29 , Available online: 2024-09-18 , https://doi.org/10.7151/dmgt.2561
Abstract:
Let $G$ be a quasi $5$-connected graph on at least 14 vertices. If there is a
vertex $x\in V_{4}(G)$ such that $G[N_{G}(x)]\cong K_{1,3}$ or $G[N_{G}(x)]
\cong C_{4}$, then $G$ can be contracted to a smaller quasi 5-connected graph
$H$ such that $0<|V(G)|-|V(H)|<4$.
Keywords:
quasi 5-connected, contraction, minor
References:
- J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York-Amsterdam-Oxford, 1982).
- M. Kriesell, A survey on contractible edges in graphs of a given vertex connectivity, Graphs Combin. 18 (2002) 1–30.
https://doi.org/10.1007/s003730200000 - M. Kriesell, Contractions, cycle double covers, and cyclic colorings in locally connected graphs, J. Combin. Theory Ser. B 96 (2006) 881–900.
https://doi.org/10.1016/j.jctb.2006.02.009 - M. Kriesell, How to contract an essentially $6$-connected graph to a $5$-connected graph, Discrete Math. 307 (2007) 494–510.
https://doi.org/10.1016/j.disc.2005.09.040 - M.D. Plummer and B. Toft, Cyclic coloration of $3$-polytopes, J. Graph Theory 11 (1987) 507–515.
https://doi.org/10.1002/jgt.3190110407 - C. Thomassen, Kuratowski's theorem, J. Graph Theory 5 (1981) 225–241.
https://doi.org/10.1002/jgt.3190050304 - C. Thomassen, Nonseparating cycles in $k$-connected graphs, J. Graph Theory 5 (1981) 351–354.
https://doi.org/10.1002/jgt.3190050403 - W.T. Tutte, A theory of $3$-connected graphs, Indag. Math. (N.S.) 64 (1961) 441–455.
https://doi.org/10.1016/S1385-7258(61)50045-5
Close