Linking four vertices in graphs of large connectivity

DOI10.1016/J.JCTB.2021.12.007MaRDI QIDQ2668016zbMATH OpenOpenAlexFDO

Authors Koyo Hayashi

Publication date 3 March 2022

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.jctb.2021.12.007

zbMATH Keywords

connectivitylinkagerooted subdivisiontwo-paths theorem

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Linkage for the diamond and the path with four vertices
• Subdivisions in planar graphs
• Connectivity for kite-linked graphs
• Nonseparating K₄‐subdivisions in graphs of minimum degree at least 4
• On \(H\)-linked graphs

Cites work

• 2-linked graphs
• 7-connected graphs are 4-ordered
• A Polynomial Solution to the Undirected Two Paths Problem
• An improved linear edge bound for graph linkages
• Applications of Menger's graph theorem
• Connectivity for kite-linked graphs
• Disjoint paths in graphs
• Disjoint paths in graphs. I: 3-planar graphs and basic obstructions
• Disjoint paths in graphs. II: A special case
• Disjoint paths in graphs. III: Characterization
• Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen
• Graph minors. IX: Disjoint crossed paths
• Graph minors. XIII: The disjoint paths problem
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Hajos' graph-coloring conjecture: Variations and counterexamples
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Linkage for the diamond and the path with four vertices
• On the Computational Complexity of Combinatorial Problems
• On the Existence of Certain Configurations within Graphs and the 1-Skeletons of Polytopes
• Reducing Hajós' 4-coloring conjecture to 4-connected graphs
• Subdivisions in planar graphs
• The Kelmans-Seymour conjecture. I: Special separations
• The Kelmans-Seymour conjecture. II: 2-vertices in \(K_4^-\)
• The Kelmans-Seymour conjecture. III: 3-vertices in \(K_4^-\)
• The Kelmans-Seymour conjecture. IV: A proof
• Topological minors in graphs of large girth
• Topological subgraphs in graphs of large girth

Cited in

(4)

• Linkage for the diamond and the path with four vertices
• scientific article; zbMATH DE number 512928 (Why is no real title available?)
• Chasing tripods to obtain a rooted subdivision
• Improved algorithms for graph four-connectivity

This page was built for publication: Linking four vertices in graphs of large connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2668016)