Skip to main content
deleted 213 characters in body
Source Link
Claus
  • 6.9k
  • 4
  • 25
  • 45

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.
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 itthem 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.

For background and motivation, I suspect thatUPDATE:
Updating this might be useful for characterizing projective planarity through the Colin de Verdière graph invariantquestion based on a great comment from Martin Winter. If it turnsAs he points out that (some of) these 35 forbidden minors have, the Colin de Verdière invariantnumber $\mu>5$. Because, in one direction,
$${\rm projective\ planarity } \Rightarrow \mu\leq5$$
is a well established result. Now if$\mu$ is known and $\mu>5$ would hold$\mu=4$ for one or morea handful of thethese 35 forbiddenforbidden minors, this could help establish the other direction and hence a full characterizatione. (Similar to how planarityg. the disjoint unions of $\Leftrightarrow$$K_5$ and $\mu\leq3$ was established)$K_{3,3}$.

(Just in case you are interested in additional background about this graph invariant Interestingly, seeas 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.

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 it for a while now, but could not find anything.

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

For background and motivation, I suspect that this might be useful for characterizing projective planarity through the Colin de Verdière graph invariant. If it turns out that (some of) these 35 forbidden minors have Colin de Verdière invariant $\mu>5$. Because, in one direction,
$${\rm projective\ planarity } \Rightarrow \mu\leq5$$
is a well established result. Now if $\mu>5$ would hold for one or more of the 35 forbidden minors, this could help establish the other direction and hence a full characterization. (Similar to how planarity $\Leftrightarrow$ $\mu\leq3$ was established)

(Just in case you are interested in additional background about this graph invariant, see Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs?)

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.

edited title
Link
Claus
  • 6.9k
  • 4
  • 25
  • 45

Graph embeddings in the projective plane: for the 35 forbidden graph minors, aredo we know their Colin de Verdière invariants knownnumbers?

Source Link
Claus
  • 6.9k
  • 4
  • 25
  • 45

Graph embeddings in the projective plane: the 35 forbidden graph minors, are their Colin de Verdière invariants known?

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 it for a while now, but could not find anything.

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

For background and motivation, I suspect that this might be useful for characterizing projective planarity through the Colin de Verdière graph invariant. If it turns out that (some of) these 35 forbidden minors have Colin de Verdière invariant $\mu>5$. Because, in one direction,
$${\rm projective\ planarity } \Rightarrow \mu\leq5$$
is a well established result. Now if $\mu>5$ would hold for one or more of the 35 forbidden minors, this could help establish the other direction and hence a full characterization. (Similar to how planarity $\Leftrightarrow$ $\mu\leq3$ was established)

(Just in case you are interested in additional background about this graph invariant, see Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs?)