The circumference of a graph with no K₃,t-minor

DOI10.1016/J.JCTB.2006.02.006MaRDI QIDQ859611zbMATH OpenOpenAlexFDO

Authors Guantao Chen, Laura Sheppardson, Xingxing Yu, Wenan Zang

Publication date 16 January 2007

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

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

zbMATH Keywords

connectivitycyclepath

Mathematics Subject Classification ID

Paths and cycles (05C38)

Review text

Let \(t\) be any integer such that \(t\geq 3\). The authors show that if \(G\) is a 3-connected graph with \(n\) nodes that contains no \(K_{3,t}\)-minors, then \(G\) has a cycle of length at least \(n^{r(t)}\), where \(r(t)= \log_{8t}(t-1)^2\); and if \(G\) is a 2-connected graph with \(n\) nodes that contains no \(K_{2,t}\)-minors, then \(G\) has a cycle of length at least \(n/t^{t-1}\).

Recommendations

• The circumference of a graph with no \(K_{3,t}\)-minor. II
• The circumference of a class of 3-connected graphs
• scientific article; zbMATH DE number 4189767
• On the circumference of 3-connected graphs
• scientific article; zbMATH DE number 147638
• scientific article; zbMATH DE number 193589
• On the circumference of 3-connected cubic triangle-free plane graphs
• Degree bounds for the circumference of 3‐connected graphs
• On the circumference of 2-connected \(\mathcal{P}_{3}\)-dominated graphs
• scientific article; zbMATH DE number 4101248

Cites work

• 4-connected projective planar graphs are Hamiltonian
• \(K_{a,k}\) minors in graphs of bounded tree-width
• A theorem on paths in planar graphs
• A Theorem on Planar Graphs
• Convex programming and circumference of 3-connected graphs of low genus
• Disjoint paths, planarizing cycles, and spanning walks
• Five-connected toroidal graphs are Hamiltonian
• Hamilton paths in toroidal graphs
• scientific article; zbMATH DE number 4110708 (Why is no real title available?)
• scientific article; zbMATH DE number 3414331 (Why is no real title available?)
• Long cycles in 3-connected graphs
• Long cycles in 3‐connected graphs in orientable surfaces
• Long cycles in graphs on a fixed surface
• Longest cycles in 3-connected planar graphs
• Polytopes, graphs, and complexes
• Shortness exponents of families of graphs
• Simple paths on polyhedra
• The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices
• Typical subgraphs of 3- and 4-connected graphs

Cited in

(10)

• The circumference of a graph with no \(K_{3,t}\)-minor. II
• Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey
• A characterization of \(K_{2,4}\)-minor-free graphs
• Large \(W_k\)- or \(K_{3,t}\)-minors in 3-connected graphs
• Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs
• Every longest circuit of a 3‐connected,K_3,3‐minor free graph has a chord
• Circumference and pathwidth of highly connected graphs
• Toughness of \(K_{a,t}\)-minor-free graphs
• Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs
• Uniform polynomial kernel for deletion to \(K_{2,p}\) minor-free graphs

This page was built for publication: The circumference of a graph with no \(K_{3,t}\)-minor

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