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.

$\endgroup$
  • $\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 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 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 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 Dollinger Aug 13 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 at 8:57
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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot for a great answer! Very clear and super helpful. Very much appreciated $\endgroup$ – Claus Dollinger Aug 15 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.