 # A characterization of \$K_{2,4}\$-minor-free graphs

Research paper by M. N. Ellingham, Emily A. Marshall, Kenta Ozeki, Shoichi Tsuchiya

Indexed on: 19 Feb '16Published on: 19 Feb '16Published in: Mathematics - Combinatorics

#### 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 \$n \ge 5\$, \$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_iy_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. 