Induced paths in 5-connected graphs

DOI10.1002/1097-0118(200101)36:1%3C52::AID-JGT5%3E3.0.CO;2-NMaRDI QIDQ2708795zbMATH OpenOpenAlexFDO

Authors Matthias Kriesell

Publication date 8 January 2002

Full work available at URL https://doi.org/10.1002/1097-0118(200101)36:1%3C52::aid-jgt5%3E3.0.co;2-n

zbMATH Keywords

connectivityinduced cycleinduced path

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Connectivity (05C40)

Recommendations

• Non-separating paths in 4-connected graphs
• A note on Lovász removable path conjecture
• A weaker version of Lovász' path removal conjecture
• Nonseparating cycles avoiding specific vertices
• scientific article; zbMATH DE number 568792

Cites work

• 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

Cited in

(25)

• 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)