An improved linear edge bound for graph linkages

DOI10.1016/j.ejc.2004.02.013zbMath1056.05091OpenAlexW2019624146MaRDI QIDQ1767622

Publication date: 8 March 2005

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2004.02.013

zbMATH Keywords

paths $k$-linked

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40)

Related Items (61)

Every $(13k - 6)$-strong tournament with minimum out-degree at least $28k - 13$ is $k$-linked ⋮ Dynamic coloring of graphs having no $K_5$ minor ⋮ Rooted minor problems in highly connected graphs ⋮ Linkage for the diamond and the path with four vertices ⋮ Locating sets of vertices on Hamiltonian cycles ⋮ Number of Cliques in Graphs with a Forbidden Subdivision ⋮ Combined Degree and Connectivity Conditions for $H$-Linked Graphs ⋮ A new upper bound on the chromatic number of graphs with no odd $K_t$ minor ⋮ Nonseparating Cycles Avoiding Specific Vertices ⋮ On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture ⋮ Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments ⋮ Characterization of $(m, n)$-linked planar graphs ⋮ On Modulo Linked Graphs ⋮ Some recent progress and applications in graph minor theory ⋮ Linking four vertices in graphs of large connectivity ⋮ On the maximum degree of path-pairable planar graphs ⋮ Cycle lengths in randomly perturbed graphs ⋮ A minimum degree condition forcing a digraph to be k-linked ⋮ The Erdős-Pósa property for clique minors in highly connected graphs ⋮ A graph minor condition for graphs to be $k$-linked ⋮ On low degree $k$-ordered graphs ⋮ The linkedness of cubical polytopes: beyond the cube ⋮ Optimal connectivity for fat-triangle linkages ⋮ Recent progress towards Hadwiger's conjecture ⋮ On linkedness in the Cartesian product of graphs ⋮ Forcing a sparse minor ⋮ Degree conditions for the existence of vertex-disjoint cycles and paths: a survey ⋮ Improved results on linkage problems ⋮ Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor ⋮ On large semi-linked graphs ⋮ Linkedness and Ordered Cycles in Digraphs ⋮ Linked graphs with restricted lengths ⋮ Highly linked tournaments ⋮ An improved linear connectivity bound for tournaments to be highly linked ⋮ Minimum degree conditions for $H$-linked graphs ⋮ The extremal function for 3-linked graphs ⋮ A weaker version of Lovász' path removal conjecture ⋮ Degree conditions on distance 2 vertices that imply $k$-ordered Hamiltonian ⋮ Linkability in iterated line graphs ⋮ Forcing unbalanced complete bipartite minors ⋮ The extremal function for $K_{9}$ minors ⋮ Non-zero disjoint cycles in highly connected group labelled graphs ⋮ 4-connected triangulations and 4-orderedness ⋮ Rank-width and tree-width of $H$-minor-free graphs ⋮ 7-connected graphs are 4-ordered ⋮ Balanced decomposition of a vertex-colored graph ⋮ Connectivities for $k$-knitted graphs and for minimal counterexamples to Hadwiger's conjecture ⋮ The linkedness of cubical polytopes: the cube ⋮ Implications among linkage properties in graphs ⋮ On linkages in polytope graphs ⋮ Parity Linkage and the Erdős–Pósa Property of Odd Cycles through Prescribed Vertices in Highly Connected Graphs ⋮ Minimum degree and pan-$k$-linked graphs ⋮ Linear connectivity forces large complete bipartite minors ⋮ Parity Linkage and the Erdős-Pósa Property of Odd Cycles Through Prescribed Vertices in Highly Connected Graphs ⋮ $(2k+1)$-connected tournaments with large minimum out-degree are $k$-linked ⋮ A fan-type result on $k$-ordered graphs ⋮ Minimum degree condition for a graph to be knitted ⋮ Distributing vertices on Hamiltonian cycles ⋮ Highly linked tournaments with large minimum out-degree ⋮ Connectivity for Kite-Linked Graphs ⋮ Rooted topological minors on four vertices

Cites Work

This page was built for publication: An improved linear edge bound for graph linkages