2
$\begingroup$

I am interested in a certain class of graphs but have very little graph theory background, I was hoping that you guys could poke me in the right direction. The class of graphs is as follows:

  • Multi-graph
  • Connected components are directed Euler graphs
  • Minimal degree is $4$
  • Bipartite
  • We are given an embedding in $X$, a compact orientable surface of genus $g$.
  • The faces of the graph (when considering said embedding) are $4$-colourable.

I'm interested in any property of these graphs!

Thanks in advance!

$\endgroup$
11
  • $\begingroup$ If the graph isn't planar, then what do you mean by the dual graph? $\endgroup$
    – Gerry Myerson
    Mar 6, 2012 at 22:38
  • $\begingroup$ Sorry, dual when it's given the embedding in the surface of genus $g$. I will fix this now. $\endgroup$
    – Harry
    Mar 6, 2012 at 22:43
  • $\begingroup$ Bump for information. $\endgroup$
    – Harry
    Mar 8, 2012 at 14:03
  • $\begingroup$ One last bump for info. $\endgroup$
    – Harry
    Mar 19, 2012 at 16:44
  • 1
    $\begingroup$ You might get better answers if you say why you became interested in this particular group of properties. Do these graphs arise in some problem you are trying to solve? $\endgroup$
    – MJD
    May 4, 2012 at 13:30

2 Answers 2

Reset to default
1
$\begingroup$

OP has clarified in the comments that some equations are wanted.

Assuming that the embedding in $X$ is a 2-cell embedding (that is, that each region is homeomorphic to a disk) we have Euler's formula, $$v-e+f=2-2g$$ where $v,e,f$ are the number of vertices, edges, and faces, respectively.

For any graph, $2e=\sum_x d(x)$, the sum over all vertices $x$ of the degree of $x$. Since the minimal degree is 4, we get $$e\ge2v$$

I think the 4-colorability gives another inequality relating these invariants, but I'm not remembering how to find it.

$\endgroup$
3
  • $\begingroup$ It is not necessarily connected - shouldn't it be $v - e + f = 1 - 2g + k$ where $k$ is the number of connected components? Also I would really appreciate it if you could post the $4$-colourability inequality. I've thinking of getting Topological graph theory by Tucker and Gross, is this a good idea? $\endgroup$
    – Harry
    May 13, 2012 at 10:00
  • 1
    $\begingroup$ How can it be an Euler graph, if it's not connected? You may find something of interest in web.science.mq.edu.au/~chris/topology/chap06.pdf $\endgroup$
    – Gerry Myerson
    May 13, 2012 at 12:47
  • $\begingroup$ Doh! All connected components should be Euler graphs. Fixed question. Thanks for link - will read. $\endgroup$
    – Harry
    May 13, 2012 at 15:34
1
$\begingroup$

This is not a complete answer, but a sketchy response to one of Gerry Myerson's comments. Yes, infinitely many graphs satisfy the listed conditions.

Fisk and Mohar [JCTA 1994] proved that any undirected graph $G$ with the following properties is 4-colorable:

  • The shortest cycle in $G$ has length at least four.
  • $G$ can be embedded on a surface of genus $g$.
  • The shortest separating cycle in the embedding of $G$ has length at least $1000\,\log_2(g+1)$. A cycle is separating if it cuts the surface into two pieces. (The constant $1000$ is a conservative estimate; Fisk and Mohar prove the existence of an appropriate constant, but don't give any explicit value.)

It is fairly easy to construct arbitrarily large graphs $G$ that satisfy these requirements by subdividing any triangulation of the surface. The faces of the dual graph $G^*$ are 4-colorable (by definition of "dual"). Subdividing each edge of $G^*$ with a new vertex makes the dual graph bipartite. Finally, replacing each undirected edge with a pair of opposing directed edges makes the graph Eulerian with minimum degree $4$.

$\endgroup$

You must log in to answer this question.

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