A characterization of K₂,4-minor-free graphs

DOI10.1137/140986517MaRDI QIDQ2808156zbMATH OpenOpenAlexFDO

Authors Emily A. Marshall, Kenta Ozeki, Shoichi Tsuchiya, M. N. Ellingham

Publication date 26 May 2016

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.4632

zbMATH Keywords

excluded minors

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Connectivity (05C40) Structural characterization of families of graphs (05C75) Graph minors (05C83)

Abstract: We provide a complete structural characterization of $K_{2,4}$-minor-free graphs. The $3$-connected $K_{2,4}$-minor-free graphs consist of nine small graphs on at most eight vertices, together with a family of planar graphs that contains $K_4$ and, for each $nge5$, $2n-8$ nonisomorphic graphs of order $n$. To describe the $2$-connected $K_{2,4}$-minor-free graphs we use $xy$-outerplanar graphs, graphs embeddable in the plane with a Hamilton $xy$-path so that all other edges lie on one side of this path. We show that, subject to an appropriate connectivity condition, $xy$-outerplanar graphs are precisely the graphs that have no rooted $K_{2,2}$-minor where $x$ and $y$ correspond to the two vertices on one side of the bipartition of $K_{2,2}$. Each $2$-connected $K_{2,4}$-minor-free graph is then (i) outerplanar, (ii) the union of three $xy$-outerplanar graphs and possibly the edge $xy$, or (iii) obtained from a $3$-connected $K_{2,4}$-minor-free graph by replacing each edge $x_i{y}_i$ in a set $x_1{y}_1,x_2{y}_2,ldots,x_k{y}_k$ satisfying a certain condition by an $x_i{y}_i$-outerplanar graph.

Recommendations

• Rooted K₄-minors
• Excluded-minor characterization of apex-outerplanar graphs
• Hamiltonicity of planar graphs with a forbidden minor
• \(K_4\)-minor-free induced subgraphs of sparse connected graphs
• Characterization of cyclically-4-connected cubic graphs without \(K_{4,4}\)-minor

Cites work

• A characterization of 3-connected graphs containing a given graph
• Decomposition of regular matroids
• Excluding a small minor
• Face covers and the genus problem for apex graphs
• Graph minors. IX: Disjoint crossed paths
• Rooted K₄-minors
• Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs
• The circumference of a graph with no \(K_{3,t}\)-minor
• The edge-density for \(K_{2,t}\) minors
• The extremal function for unbalanced bipartite minors
• Toughness of \(K_{a,t}\)-minor-free graphs

Cited in

(15)

• Rooted K₄-minors
• Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs
• Framed 4-valent graph minor theory II: Special minors and new examples
• Distance Constrained Labelings of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msub><mml:mi>K</mml:mi><mml:mn>4</mml:mn></mml:msub></mml:math>-minor Free Graphs
• Excluded-minor characterization of apex-outerplanar graphs
• The ratio of the numbers of odd and even cycles in outerplanar graphs
• Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
• A Brooks-type bound for squares of \(K_{4}\)-minor-free graphs
• Distance constrained labelings of \(K_{4}\)-minor free graphs
• Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey
• The characterization of graphs with no 2-connected spanning subgraph of \(V_8\) as a minor
• A note on highly connected \(K_{2, \ell}\)-minor free graphs
• Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs
• Untangling circular drawings: algorithms and complexity
• Vertex partitions of \(K_{4,4}\)-minor free graphs

This page was built for publication: A characterization of \(K_{2,4}\)-minor-free graphs

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