A vertex k-coloring of a graph is a coloring of the vertices by k colors, and an edge k-coloring is a coloring of the edges by k colors. A coloring with two colors (usually black and white) will be called a (vertex or edge) bicoloring. If the colors mentioned are treated as weights assigned to vertices or edges of a graph, such a graph will be called a weighted graph

As well as a plane or sphere, we may consider other smooth surfaces, which can be orientable, and like the sphere have an inside and an outside, or can be non-orientable, such as the projective plane or Klein bottle. An orientable surface can be regarded as a sphere with g handles (g = 0,1,2,...), and the number of handles g is the genus of the surface. For a torus or "sphere with a handle", g = 1, for a double torus g = 2, etc. The simplest non-orientable surface is the projective plane, which may be regarded as a sphere with antipodes identified, or as a hemisphere with opposite peripheral points identified, or as a sphere with a cross-cap (Coxeter and Moser, 1980). For a non-orientable surface without boundary, the genus g is given by the formula g = 2-c, and for an orientable surface without boundary by the formula g = [(2-c)/ 2].

An embedding of a graph G in a surface can be constructed by the method known as the Edmonds algorithm, named after J. Edmonds who described it in 1960. For an input graph G given by a list of unordered pairs (its edges) the LinKnot function fEdmonds (webMathematica fEdmonds) calculates the labelled polygons for its embedding, the Euler characteristic of the surface and its genus. From that output we can construct the corresponding embedding. For example, for K3,3 given by the list of unordered pairs, by using the function fEdmonds we obtain the result 

{{1,4,2,5,3,6},{1,4,3,6,2,5},{1,5,3,4,2,6}},0,1}.

Because the surface has Euler characteristic 0 and genus 1, it is a torus on which we place the three labelled hexagons obtained. 

Hence, the embedding of the non-planar graph K3,3 on a torus is given by 

{{1,6,4,5},{2,6,4,5},{3,6,4,5},{4,1,2,3},{5,1,2,3},{6,1,2,3}}.
In a similar way we obtain the embedding 
{{1,2,4,3},{1,2,5,4},{1,3,2,5},{1,4,3,5},{2,3,5,4}},
of the non-planar graph K5 on a torus. 

This basic introduction to graph theory is written according to the books by R.A. Wilson (2002), N.D. Gilbert and T. Porter (1994), with some changes in definitions, and certain additions.
 
 

PreviousContentsNext