Non-separating subgraphs after deleting many disjoint paths
type: Item
instance of: scholarly article
title: Non-separating subgraphs after deleting many disjoint paths
zbMATH Open document ID: 1218.05079
author: Ken-ichi Kawarabayashi
author: Kenta Ozeki
published in: Journal of Combinatorial Theory. Series B
publication date: 2011-01-14T00:00:00Z
review text: The following conjecture is raised in the paper: There exists a function \(f=f(k,l)\) such that for every \(f(k,l)\)-connected graph \(G\) and for every distinct vertices \(s\) and \(t\) in \(G\), there are \(k\) internally disjoint paths \(P_{1},\dots,P_{k}\) with endpoints \(s\) and \(t\) such that \(G-\bigcup_{i=1}^{k} V(P_{i})\) is \(l\)-connected. Setting \(k=1\) reduces the problem to a conjecture of Lovász that has been settled for \(l=1,2.\) The authors generalize some known results by showing that \(f(k,1)=2k+1\), the value \(2k+1\) being the best possible, and \(f(k,2)\leq 3k+2\).
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5836654
zbMATH Keywords: non-separating subgraphs
zbMATH Keywords: Lovász conjecture
reviewed by: Peter Horák
MaRDI profile type: Publication
full work available at URL: j.jctb.2010.10.002
OpenAlex ID: W2113287106
cites work: Graph connectivity after path removal
cites work: Non-separating paths in 4-connected graphs
cites work: A weaker version of Lovász' path removal conjecture
cites work: Induced paths in 5-connected graphs
cites work: Normal hypergraphs and the perfect graph conjecture. (Reprint)
cites work: Nonseparating cycles inK-Connected graphs
cites work: How to Draw a Graph
cites work: Bridges in Highly Connected Graphs
DOI: 10.1016/J.JCTB.2010.10.002
description: scientific article; zbMATH DE number 5836654