Face colorings of embedded graphs (Q3335810)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3867365
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Face colorings of embedded graphs |
scientific article; zbMATH DE number 3867365 |
Statements
Face colorings of embedded graphs (English)
0 references
1984
0 references
evenly spanned graphs
0 references
splitting
0 references
Tait coloring
0 references
packed 4-coloring
0 references
0.800597071647644
0 references
0.7666153907775879
0 references
0.766338050365448
0 references
A subgraph H evenly spans a graph G if (i) each vertex of G is of positive even degree in H, and (ii) in each component of H there are an even number of vertices which are of odd degree in G. Now let \(A=A_ 1\cup A_ 2\) be a bipartition of the set of edges incident with vertex v in G; the splitting of G with respect to this bipartition is the graph formed by deleting v from the vertex set and A from the edge set of G, adding two new vertices \(v_ 1\) and \(v_ 2\), and adding the edges \(\{[v_ i,u]| [v,u]\in A_ i\}, i=1,2\) and the edge \([v_ 1,v_ 2]\). If G' can be obtained from G by a sequence of splittings, we call G' a splitting of G. A Tait coloring of a cubic graph is a proper 3-coloring of its edges. A proper k-coloring of the faces of an imbedding of G into a surface is packed if, for each vertex of G, the set of faces incident with v receives at least three distinct colors. For G a graph with minimum degree at least 3, the author shows the following to be equivalent: (i) G is evenly spanned. (ii) G has a splitting which is a Tait-colorable cubic graph. (iii) G imbeds on some orientable surface with a packed 4-coloring of the faces. (iv) G imbeds on some surface with a packed 4-coloring of the faces. (v) G imbeds on some surface with a packed 3-coloring of the faces. This extends a theorem of \textit{W. T. Tutte} [Proc. Lond. Math. Soc., II. Ser. 51, 474-483 (1949; Zbl 0033.308)], for cubic graphs, to non-cubic graphs. The author also observes that almost all graphs are evenly spanned (that is, the probability approaches 1 as the order of G approaches infinity.)
0 references