FORBIDDEN MINORS FOR APEX GRAPHS

MAKOTO OZAWA, YUKIHIRO TSUTSUMI, AND TAKATOSHI KUSAMA

Abstract. We will characterize the obstruction set for apex graphs.

1. Introduction

A graph is n-apex if it can be made planar by removing at most n vertices. Let A_{n} be the set of n-apex graphs and A_{−1} be the set of outerplanar graphs. Proposition 1.1. 1. A graph G is planar if and only if G ∈ A_{0}.

2. G ∉ A_{n} if and only if for any n-vertices v_{1}, …, v_{n} ∈ V (G), G−{v_{1}, …, v_{n}} ∉ A_{0}

3. A_{n} ⊃ A_{n−1} ⊃ ⋯ ⊃ A_{1} ⊃ A_{0} ⊃ A_{−1}.

4. For any G ∈ A_{n}, any minor of G is also an element of A_{n}.

Therefore, the obstruction set Ω(A_{n}) for A_{n} can be defined. Theorem 1.2 (Chartrand-Harary). Ω(A_{−1}) = {K_{4}, K_{2,3}}. Theorem 1.3 (Kuratowski). Ω(A_{0}) = {K_{5}, K_{3,3}}.

We will prove the following conjectures. Conjecture 1.4. Ω(A_{1}) = (Ω(A_{0}) ∐ Ω(A_{0})) ∪ (K_{6}-family) ∪ (K_{3,3,1}-family).

Note that Robertson, Seymour, and Thomas ([6]) proved that the obstruction set Ω(LL) for the set LL of linkless graphs is equal to the Petersen family. Conjecture 1.5. (?) Ω(A_{2}) = (Ω(A_{i}) ∐ Ω(A_{j})) ∪ (K_{7}-family) ∪ (K_{3,3,1,1}-family), where {i, j} = {1, 2}.

In general, we show the following. Conjecture 1.6. (?) For any connected graph G ∈ Ω(A_{n}) and any v ∈ V (G), G − v is a subdivision of an element of Ω(A_{n−1}).

Thus, any element of A_{n} can be obtained from G ∈ A_{n−1} by adding one vertex.

2. Ω(A_{1})

Proposition 2.1. A_{1} ⊂ LL and Ω(A_{1}) ⊃ Ω(LL). Remark 2.2. A_{1} ≠ LL. Lemma 2.3. If Ω(A_{1}) ∩ LL = Ω(A_{0}) ∐ Ω(A_{0}), then Ω(A_{1}) = (Ω(A_{0}) ∐ Ω(A_{0})) ∪ Ω(LL).

1991 Mathematics Subject Classification. Primary 57M25, 57M15; Secondary 05C83, 05C10.

Key words and phrases. spatial graph, graph minor.

The second author was partially supported by Research Fellowships of the Japan Society for the Promotion of Science for Young Scientists.

Proof. Suppose that Ω(A_{1}) ∩ LL = Ω(A_{0}) ∐ Ω(A_{0}).

Let G ∈ Ω(A_{1}) be a connected graph. Then, by the supposition, G ∉ LL. If G ∉ Ω(LL), then G has a proper minor H ∈ Ω(LL). On the other hand, H ∈ A_{1} since G ∈ Ω(A_{1}). Thus H ∈ LL since A_{1} ⊂ LL. This contradicts that H ∈ Ω(LL). Therefore, G ∈ Ω(LL).

Next, let G ∈ Ω(A_{1}) be a disconnected graph. Then by Lemma 2.4, G ∈ Ω(A_{0}) ∐ Ω(A_{0}).

Hence, Ω(A_{1}) ⊂ (Ω(A_{0}) ∐ Ω(A_{0})) ∪ Ω(LL). On the other hand, Ω(A_{1}) ⊃ Ω(A_{0}) ∐ Ω(A_{0}) by Lemma 2.4, and Ω(A_{1}) ⊃ Ω(LL) by Proposition 2.1. Therefore, Ω(A_{1}) = (Ω(A_{0}) ∐ Ω(A_{0})) ∪ Ω(LL).

Lemma 2.4. Let G ∈ Ω(A_{1}) be a disconnected graph. Then G is a disjoint union K ∐ K′, where K, K′ ∈ Ω(A_{0}).

Proof. Let G = G_{1} ∪ ⋯ ∪ G_{n} ∈ Ω(A_{1}), where G_{i} (i = 1, …, n) is connected. Then G_{i} ∈ A_{1} (i = 1, …, n) since G_{i} is a proper minor of G. If G_{i} ∈ A_{0} for all i, then G ∈ A_{0}, a contradiction. Hence without loss of generality, we may assume that G_{1} ∈ A_{1} − A_{0} and there exists a vertex v_{1} ∈ V (G_{1}) such that G_{1} − v_{1} ∈ A_{0}. Since G − v_{1} ∈ A_{1} − A_{0}, there exists a non-planar component of G − G_{1}, say G_{2}. Then, there exists a vertex v_{2} ∈ V (G_{2}) such that G_{2} − v_{2} ∈ A_{0}.

Suppose that n ≥ 3. Then for any v_{3} ∈ V (G_{3}), G − v_{3} ∈ A_{1}. However, this contradicts that G_{1} ∈ A_{1}−A_{0} and G_{2} ∈ A_{1}−A_{0}. Therefore n = 2 and G = G_{1}∪G_{2}.

Since G_{1} ∉ A_{0} and G_{2} ∉ A_{0}, there exist Kuratowski graphs K_{1} ⊂ G_{1} and K_{2} ⊂ G_{2}. If G_{1} ≠ K_{1}, then for any edge e_{1} ∈ E(G_{1}) − E(K_{1}), G − e ∈ A_{1}. This is a contradiction since G − e ⊃ K_{1} ∪ K_{2}. Hence, G_{1} = K_{1}. Similarly, G_{2} = K_{2}. Hence, both of G_{1} and G_{2} are K_{5} or K_{3,3} by the minor minimality of G.

Hereafter, we assume that G ∈ Ω(A_{1}) is connected, and will show that G is in the Petersen family.

Lemma 2.5. Let G ∈ Ω(A_{1}) be connected, and suppose that G contains two Kuratowski graphs K_{1} and K_{2}. Then K_{1} ∩ K_{2} ≠ ∅.

Proof. If K_{1} ∩ K_{2} = ∅, then G contains K_{1} ∐ K_{2} ∈ Ω(A_{1}) as a proper minor.

Lemma 2.6. For G ∈ Ω(A_{1}), G is 2-connected.

Proof. Suppose that G has a cut vertex v, and put G = G_{1} ∪ G_{2} and G_{1} ∩ G_{2} = v. Since G_{1} and G_{2} are proper subgraph of G, we have that G_{1} ∈ A_{1} and G_{2} ∈ A_{1}.

Claim 2.7. G_{1} ∉ A_{0} and G_{2} ∉ A_{0}.

Proof. Suppose that G_{1} ∈ A_{0} and G_{2} ∈ A_{0}. Then G = G_{1} ∪_{v} G_{2} ∈ A_{0}, a contradiction.

Hence without loss of generality, we may assume that G_{1} ∈ A_{1} − A_{0}.

Claim 2.8. G_{2} ∉ A_{0}.

Proof. Suppose that G_{2} ∈ A_{0}. Let e be an edge of G_{2} which incidents to v. Then G − e ∈ A_{1} and there exists a vertex v_{1} ∈ G_{1} such that (G − e) − v_{1} ∈ A_{0} since G_{1} ∈ A_{1}. If v_{1} = v, then G − v = G − v_{1} = (G − e) − v_{1} ∈ A_{0} and G ∈ A_{1}. This is a contradiction. Otherwise, G − v_{1} ∈ A_{0} since G − v_{1} = (G_{1} − v_{1}) ∪_{v} G_{2} and G_{1} − v_{1} ⊂ (G − e) − v_{1} ∈ A_{0}. Thus G ∈ A_{1} and this is also a contradiciton.

Hence G_{1} ∈ A_{1} − A_{0} and G_{2} ∈ A_{1} − A_{0}, and both of G_{1} and G_{2} contain Kuratowski graphs K_{1} and K_{2} respectively.

Claim 2.9. G_{1} = K_{1} or G_{2} = K_{2}.

Proof. Suppose that G_{1} ≠ K_{1} and G_{2} ≠ K_{2}. Let e_{1} ∈ E(G_{1}) − E(K_{1}) and e_{2} ∈ E(G_{2})−E(K_{2}). Then G−e_{1} ∈ A_{1} and there exists a vertex v′ ∈ V (G−e_{1}) such that (G−e_{1})−v′ ∈ A_{0}. Since G_{1} −e_{1} ⊃ K_{1} and G_{2} ⊃ K_{2}, v′ ∈ V (G_{1} −e_{1})∩V (G_{2}). Thus v′ = v. Hence G_{2}−v ⊂ (G−e_{1})−v ∈ A_{0}. Similarly for e_{2}, we have G_{1}−v ∈ A_{0}. Therefore G−v = (G_{1} −v)∪(G_{2} −v) ∈ A_{0} and G ∈ A_{1}. This is a contradiction.

Hence without loss of generality, we may assume that G_{2} = K_{2}. Thus G_{2} − v ∈ A_{0}. If G_{1} − v ∈ A_{0}, then G − v = (G_{1} − v) ∪ (G_{2} − v) ∈ A_{0} and G ∈ A_{1}, a contradiction. Hence G_{1}−v ∉ A_{0}, and there exists a Kuratowski graph K′_{1} ⊂ G_{1}−v. Let e ∈ E(G_{1}) − E(K_{1}) which incidents to v. Then G − e ∈ A_{1} and there exists a vertex v′ ∈ V (G − e) such that (G − e) − v ∈ A_{0}. Since G_{1} − e ⊃ K′_{1} and G_{2} = K_{2}, v′ ∈ V (G_{1} − e) ∩ V (G_{2}). Thus v′ = v. However, G − v = (G − e) − v ∈ A_{0} and hence G ∈ A_{1}. This is a contadiction.

Lemma 2.10. (?) For G ∈ Ω(A_{1}), G is Kuratowski 3-connected (equivalently, every pair of Kuratowski graphs in G communicate).

Proof. Suppose that G is not 3-connected. Then, there exist vertices v_{1} and v_{2} such that G = G_{1} ∪ G_{2} and G_{1} ∩ G_{2} = v_{1} ∪ v_{2}.

Claim 2.11. G_{1} − v_{1} ∉ A_{0} or G_{2} − v_{1} ∉ A_{0}.

Proof. Suppose that G_{1} −v_{1} ∈ A_{0} and G_{2} −v_{1} ∈ A_{0}. Then (G_{1} −v_{1})∪_{v_{2}} (G_{2} −v_{1}) ∈ A_{0} and hence {(G_{1} − v_{1}) ∪_{v_{2}} (G_{2} − v_{1})} ∗ v_{1} = G ∈ A_{1}. This is a contradiction.

Hereafter, without loss of generality, we may assume that G_{1} − v_{1} ∉ A_{0}.

Claim 2.12. G_{2} − v_{2} ∈ A_{0}.

Proof. Since G_{1} − v_{1} ∉ A_{0}, there exists a Kuratowski graph K_{1} ⊂ G_{1} − v_{1}. Let e ∈ E(G_{2}) be an edge which incidents to v_{2}. Then, G − e ∈ A_{1} and there exists a vertex v ∈ V (G − e) such that (G − e) − v ∈ A_{0}. Since K_{1} ⊂ G − e, v ∈ V (K_{1}). Moreover, if v = v_{2}, then (G − e) − v = G − v_{2} ∈ A_{0} and G ∈ A_{1}, a contradiction. Hence v ∈ V (K_{1}) − {v_{2}} and (G − e) − v ⊃ G_{2} − e ∈ A_{0}. In particular, G_{2} − e ⊃ G_{2} − v_{2} ∈ A_{0}.

Claim 2.13. G_{1} − v_{2} ∉ A_{0} or G_{2} − v_{2} ∉ A_{0}.

Proof. Similar to Claim 2.11.

By Claim 2.12 and 2.13, G_{1} − v_{2} ∉ A_{0}.

Claim 2.14. G_{2} − v_{1} ∈ A_{0}.

Proof. Similar to Claim 2.12.

Hence, we have G_{1} − v_{1} ∉ A_{0}, G_{1} − v_{2} ∉ A_{0}, G_{2} − v_{1} ∈ A_{0} and G_{2} − v_{2} ∈ A_{0}.

Claim 2.15. If G_{2} ∉ A_{0}, then both of G_{1} − v_{1} and G_{1} − v_{2} are Kuratowski graphs.

Proof. Since G_{1} − v_{1} ∉ A_{0} and G_{1} − v_{2} ∉ A_{0}, G_{1} − v_{1} and G_{1} − v_{2} contain Kuratowski graphs K_{1} and K_{2} respectively. Suppose that there exists an edge e ∈ E(G_{1}) − E(K_{1}) − E(K_{2})

3. Ω(A_{2})

Proposition 3.1 ([4]). Ω(A_{2}) ⊃ (K_{7}-family) ∪ (K_{3,3,1,1}-family).

Proposition 3.2 ([4]). F ∉ Ω(A_{2}), where F is the Foisy graph ([2]).

Since F ∈ Ω(KL), we have Ω(A_{2}) ≠ Ω(KL), where KL denotes the set of knotless graphs.

4. Colin de Verdière invariant

Colin de Verdière ([1]) introduced an invariant μ(G) of a graph G.

Theorem 4.1 ([1]). A graph G is planar if and only if μ(G) ≤ 3.

Theorem 4.2 ([3]). A graph G is linkless if and only if μ(G) ≤ 4.

Conjecture 4.3. A graph G is n-apex if and only if μ(G) ≤ 3 + n.

References

1. Y. Colin de Verdière, Sur un nouvel invariant des graphes et un critère de planarité, J. Combin. Theory Ser. B 50 (1990), 11–21; [English transl.] On a new graph invariant and a criterion for planarity, in “Graph Structure Theory” (N. Robertson, P. Seymour, Eds.), Contemporary Mathematics, pp. 137–147, American Mathematical Society, Providence, RI, 1993.

2. J. Foisy, A newly recognized intrinsically knotted graph, J. Graph Theory 43 (2003) 199–209.

3. L. Lovász and A. Schrijver, A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs, Proc. Amer. Math. Soc. 126 (1998), 1275–1285.

4. M. Ozawa and Y. Tsutsumi, Primitive spatial graphs and graph minors, preprint.

5. N. Robertson and P. Seymour, Graph minors XVI. Wagner’s conjecture, to appear.

6. N. Robertson, P. Seymour, and R. Thomas, Linkless embedding of graphs in 3-space, Bull. Amer. Math. Soc. 28 (1993), 84–89.

7. N. Robertson, P. Seymour, and R. Thomas, Kuratowski Chains, J. Combinatorial Theory, Ser. B 64 (1995), 127–154.

8. N. Robertson, P. Seymour, and R. Thomas, Petersen Family Minors, J. Combinatorial Theory, Ser. B 64 (1995), 155–184.

9. N. Robertson, P. Seymour, and R. Thomas, Sachs’ Linkless Embedding Conjecture, J. Combinatorial Theory, Ser. B 64 (1995), 185–227.

Natural Science Faculty, Faculty of Letters, Komazawa University, 1-23-1 Komazawa, Setagaya-ku, Tokyo, 154-8525, Japan

  E-mail address: ozawa@musubime.com

Faculty of Science and Technology, Department of Mathematics, Keio University, Hiyoshi 3-14-1, Kohoku-ku, Yokohama 223-8522, Japan

  E-mail address: yukihiro@math.keio.ac.jp

Department of Mathematics, School of Education, Waseda University, Nishiwaseda 1-6-1, Shinjuku-ku, Tokyo 169-8050, Japan

  E-mail address: takatoshi@helen.ocn.ne.jp