Face colorings of embedded graphs

From MaRDI portal
Publication:3335810





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











This page was built for publication: Face colorings of embedded graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3335810)