Induced paths in 5-connected graphs
\textit{C. Thomassen} [J. Graph Theory 7, 261-271 (1983; Zbl 0515.05052)] attributes to L. Lovász the conjecture that for any natural number \(k\) there exists a smallest \(f(k)\) such that any two vertices of an \(f(k)\)-connected graph are joined by an induced path, the removal of whose vertices leaves a \(k\)-connected subgraph. The author remarks that \(f(1)=3\) and proves that \(f(2)=5\). (Guantao Chen has independently proved that \(f(2)\leq 5\).) The author shows further that were the conjecture restricted to derived (line) graphs, one would have \(f(k)\leq 2k+5\). Replacing ``induced by ``shortest would alter completely the nature of the conjecture, as it is shown that given \(k>\ell>0\), there exist infinitely many graphs of connectivity \(k\) containing a pair of vertices such that the deletion of the vertex set of any shortest path joining them leaves a subgraph of connectivity \(\ell\).
- Contractible subgraphs in 3-connected graphs
- Contractible triples in 3-connected graphs
- Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
- Graph decomposition with applications to subdivisions and path systems modulo k
- Kuratowski's theorem
- Non-separating induced cycles in graphs
- Nonseparating cycles inK-Connected graphs
- Paths and edge-connectivity in graphs
- Partitions of graphs with high minimum degree or connectivity.
- Rooted complete minors in line graphs with a Kempe coloring
- Non-separating paths in 4-connected graphs
- Contractible subgraphs in 3-connected graphs
- Removable cycles in non-bipartite graphs
- Graphs with No Induced Five‐Vertex Path or Antipath
- Nonseparating cycles avoiding specific vertices
- Removable paths and cycles with parity constraints
- Spanning trees with nonseparating paths
- Exact Solution Algorithms for the Chordless Cycle Problem
- Independent paths and \(K_{5}\)-subdivisions
- Shifting paths to avoidable ones
- Finding a shortest even hole in polynomial time
- Non-separating subgraphs after deleting many disjoint paths
- A Menger-type theorem for two induced paths
- Non-separating even cycles in highly connected graphs
- Linkages and removable paths avoiding vertices
- Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
- Semidefinite programming bounds and a branch-and-bound algorithm for the chordless cycle problem
- Connectivity keeping paths containing prescribed vertices in highly connected triangle-free graphs
- Cycles through two edges in signed graphs (extended abstract)
- What is on his mind?
- Improved algorithms for perfect graphs and odd holes
- The Kelmans-Seymour conjecture. IV: A proof
- A weaker version of Lovász' path removal conjecture
This page was built for publication: Induced paths in 5-connected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2708795)
