A vertex kcoloring
of a graph is a coloring of the vertices by k colors, and an edge kcoloring
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 nonorientable, 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 nonorientable 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 crosscap (Coxeter and Moser, 1980). For a nonorientable surface without boundary, the genus g is given by the formula g = 2c, and for an orientable surface without boundary by the formula g = [(2c)/ 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 K_{3,3} given by the list of unordered pairs, by using the function fEdmonds we obtain the result
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 nonplanar graph K_{3,3} on a torus is given by
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.
