Method of 3-colouring of graphs (Q1123201)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Method of 3-colouring of graphs |
scientific article |
Statements
Method of 3-colouring of graphs (English)
0 references
1987
0 references
The author says that a colouring of a graph is three-colour if either every edge is red, or one of its halves is blue and the other half is green. Such a colouring is equivalent to partial orientation: red edges are not oriented, and two-colour edges are oriented from the blue half to the green half. The author considers three-colour colouring only for graphs that consist of the edges of a triangulation of a two-dimensional, connected, closed, orientable (or not) manifold M. Let A be a vertex of the triangulation of the manifold M. An inversion is a situation in which two half-edges, incident with vertex A and neighbouring in the sense of going round the vertex, are coloured so that one is blue and the other is green. A vertex is said to be red if all edges incident with it are red. Let \(\alpha\) be the total number of red vertices. The basic results of the paper are contained in the following two theorems. Theorem 1: Let there exist a three-colour colouring of the graph of the triangulation of manifold M. Let not all the vertices be red, and no more than two red edges be incident with each nonred vertex. If \(\alpha\)-\(\chi\) (M)\(\geq 1\), where \(\chi\) is the Euler characteristic, then in the triangulation is at least one face without red edges. Theorem 2: Let \(\mu (A_ i)\) be the number of inversions at vertex \(A_ i\), and \(\beta (A_ i)\) the number of red edges incident with it. Let \(\alpha\)-\(\chi\) (M)\(\geq 1\) and \(\mu (A_ i)+\beta (A_ i)\leq 2\) for every nonred vertex A. Then all the vertices are red. These theorems are applicable to the study of the rigidity of closed polyhedral surfaces and rod-like systems in \({\mathbb{R}}^ 3\) and rod-like systems in Riemannian manifolds, replacing the well-known Cauchy lemma.
0 references
partial orientation
0 references
triangulation
0 references
three-colour colouring
0 references
Euler characteristic
0 references
inversions at vertex
0 references
closed polyhedral surfaces
0 references
rod- like systems
0 references