17
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – M. Winter
    Aug 12, 2020 at 21:03
  • 2
    $\begingroup$ 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? $\endgroup$
    – M. Winter
    Aug 12, 2020 at 21:14
  • 1
    $\begingroup$ 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? $\endgroup$
    – M. Winter
    Aug 12, 2020 at 21:38
  • 3
    $\begingroup$ @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 $\endgroup$
    – Claus
    Aug 13, 2020 at 6:54
  • $\begingroup$ $\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. $\endgroup$
    – M. Winter
    Aug 13, 2020 at 8:57

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks a lot for a great answer! Very clear and super helpful. Very much appreciated $\endgroup$
    – Claus
    Aug 15, 2020 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.