# Graph embeddings in the projective plane: for the 35 forbidden minors, do we know their Colin de Verdière numbers?

The Graph Minor Theorem of Robertson and Seymour asserts that any minor-closed graph property is determined by a finite set of forbidden graph minors. It is a broad generalization e.g. of the Kuratowski-Wagner theorem, which characterizes planarity in terms of two forbidden minors: the complete graph $$K_5$$ and the complete bipartite graph $$K_{3,3}$$.

Embeddability of a graph in the projective plane is such a minor-closed property as well, and it is known that there are 35 forbidden minors that characterize projective planarity. All 35 minors are known, a recent reference from 2012 is, for example, https://smartech.gatech.edu/bitstream/handle/1853/45914/Asadi-Shahmirzadi_Arash_201212_PhD.pdf.
A classical reference is Graphs on Surfaces from Mohar and Thomassen, Johns Hopkins University Press 2001.

I am interested in the Colin de Verdière numbers for these 35 forbidden minors and have searched for them for a while now, but could not find anything.

Question: So I wondered whether the Colin de Verdière graph invariants for the whole set of these 35 forbidden minors are actually known? I would be grateful for any reference.

UPDATE:
Updating this question based on a great comment from Martin Winter. As he points out, the Colin de Verdière number $$\mu$$ is known and $$\mu=4$$ for a handful of these 35 forbidden minors, e.g. the disjoint unions of $$K_5$$ and $$K_{3,3}$$.

Interestingly, as outlined in his answer to a related question (Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs?), it follows that the Colin de Verdière invariant cannot provide a full characterization of graph embeddings e.g. in the projective plane.

• Can you say where in the linked thesis these 35 graphs are listed? I can find the first 24 graphs in section 1.7 and 1.8. The remaining 11 cases should be listed in Chapter V, but they seem a bit more hidden. Aug 12 '20 at 21:03
• If $\mu>5$ holds not for all forbidden minors, then we can't have "projective planarity $\Leftrightarrow$ $\mu \le 5$". So the hope is that all of them have $\mu$ larger five, or am I missing something? Aug 12 '20 at 21:14
• And correct me if this is wrong, but the thesis lists $K_5+K_5$ (disjoint union) as one of the forbidden minors, and isn't $\mu=4$ for this graph already? Aug 12 '20 at 21:38
• @M.Winter in the thesis, you should find all 35 of them in Figure 1.1 which is on page 8 of the text body and page 14 of the pdf Aug 13 '20 at 6:54
• $\mu(K_5+K_5)=\mu(K_5)$ is a consequence Theorem 2.5 in "The Colin de Verdière graph parameter" by van der Holst, Lovász, Schrijver. I also added an answere here. Aug 13 '20 at 8:57

Here's a table containing the Colin de Verdière numbers:

Name        Graph6      μ   Reason
K33 + K33               4   (components linklessly embeddable)
K5  + K33               4   (components linklessly embeddable)
K5  + K5                4   (components linklessly embeddable)
K33 . K33               4   (apex)
K5  . K33               4   (apex)

K5  . K5                4   (apex)
B3          G~wWw{      4   (apex)
C2          H~wWooF     4   (apex)
C7          G~_kY{      4   (apex)
D1          Is[CKIC[w   4   (apex)

D4          H~AyQOF     4   (apex)
D9          I]op_oFIG   4   (apex)
D12         H^oopSN     4   (apex)
D17         G~_iW{      4   (apex)
E6          Is[BkIC?w   4   (apex)

E11         I]op_oK?w   4   (apex)
E19         H~?guOF     4   (apex)
E20         H~_gqOF     4   (apex)
E27         I]op?_NAo   4   (apex)
F4          Is[?hICOw   4   (apex)

F6          Is[@iHC?w   4   (apex)
G1                      4   (apex)
K35                     4   (apex)
K45-4K2                 4   (apex)
K44-e                   5   (Petersen family and -2 argument)

K7-C4                   4   (apex)
D3          G~sghS      4   (apex)
E5          H]oxpoF     5   (Petersen family and -2 argument)
F1          H]ooXCL     4   (apex)
K1222                   4   (apex)

B7                      4   (apex)
C3                      4   (apex)
C4                      4   (apex)
D2                      4   (apex)
E2                      4   (apex)


Let me give justification. Graphs with $$\mu \leq 3$$ are planar, hence embeddable on the projective plane. So all the $$35$$ graphs have $$\mu \geq 4$$. Since apex graphs are linklessly embeddable, and linklessly embeddable graphs have $$\mu \leq 4$$, the apex graphs in this table have exactly $$\mu = 4$$. Also, a graph is linklessly embeddable iff its components are linklessly embeddable, so the first three graphs have $$\mu = 4$$.

The graphs in the Petersen family are not linklessly embeddable, so they have $$\mu \geq 5$$. $$K_{4,4}-e$$ is already in the Petersen family, and $$\mathcal E_5$$ contains $$K_{3,3,1}$$ as a subgraph. They both have $$\mu \geq 5$$.

To see they have $$\mu \leq 5$$, use Theorem 2.7 in [1]: If $$G=(V,E)$$ is a graph, and $$v$$ a vertex of $$G$$, then $$\mu(G) \leq \mu(G-v)+1$$. Since we can remove $$2$$ vertices from $$K_{4,4}-e$$ to make it planar (by making it $$K_{3,3}-e$$), it follows that $$\mu(K_{4,4}-e) \leq \mu(K_{3,3}-e)+2 = 5$$. Hence $$\mu(K_{4,4}-e)=5$$. The same line of reasoning applies to the graph $$\mathcal E_5$$.

[1] Van Der Holst, Hein, László Lovász, and Alexander Schrijver. "The Colin de Verdiere graph parameter." Graph Theory and Computational Biology (Balatonlelle, 1996) (1999): 29-85.

• Thanks a lot for a great answer! Very clear and super helpful. Very much appreciated Aug 15 '20 at 10:56