2
$\begingroup$

A planar graph $G$ has some set of embeddings $\{E_\gamma:G \hookrightarrow R^2\}$. Each of these embeddings has associated with it a geometric dual graph $G^*_\gamma$. Using $\chi$ to denote chromatic number:

Question 1: For a given graph $G$, what is known about the set of integers $\{\chi(G^*_\gamma)\}$? Is it, for instance, guaranteed to be an interval?

A similar question can be asked about cellular embeddings of $G$ on higher-genus surfaces:

Question 2: For a given $G$, what is known about the chromatic numbers of the surface duals of cellular embeddings of $G$? What about those embeddings which share the same genus?

Improve this question
$\endgroup$
1
  • $\begingroup$ I've been unable to find much work related to this question, though I suspect it's due to poor choice of query terms. I also originally posted this question to math.stackexchange/... but am guessing Mathoverflow is more appropriate. Thanks! $\endgroup$
    – JosephSlote
    Commented Dec 10, 2020 at 1:28

1 Answer 1

Reset to default
1
$\begingroup$

Regarding Question 1: you can very explicitly express the chromatic number of a dual graph, namely as the flow number of the primal graph (see for example: Wikipedia: Nowhere-zero flow).

Maybe a brief comment on the variety of the set of embeddings for a given planar graph: If $G$ is a $3$-connected planar graph, then it has a unique embedding into the plane. This result is due to Whitney and it is discussed in standard textbooks for graph theory, e.g. the book of Bondy and Murty or the one by Diestel.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .