# Properties of this class of graphs

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!

-
If the graph isn't planar, then what do you mean by the dual graph? – Gerry Myerson Mar 6 '12 at 22:38
Sorry, dual when it's given the embedding in the surface of genus $g$. I will fix this now. – Harry Mar 6 '12 at 22:43
Bump for information. – Harry Mar 8 '12 at 14:03
One last bump for info. – Harry Mar 19 '12 at 16:44
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? – MJD May 4 '12 at 13:30

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.

-
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? – Harry May 13 '12 at 10:00
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 – Gerry Myerson May 13 '12 at 12:47
Doh! All connected components should be Euler graphs. Fixed question. Thanks for link - will read. – Harry May 13 '12 at 15:34

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

-