Face colorings of embedded graphs
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.)
- Note on cycle double covers of graphs
- Closed 2-cell embeddings of 4 cross-cap embeddable graphs
- On \(d\)-diagonal colorings of embedded graphs of low maximum face size
- Facial packing vertex-coloring of subdivided plane graphs
- The closed 2-cell embeddings of 2-connected doubly toroidal graphs
- Nowhere-zero 4-flows and cycle double covers
- Cycle double covers and non-separating cycles
- Face-width of embedded graphs
- Strong circuit double cover of some cubic graphs
- Face 2-Colorable Embeddings with Faces of Specified Lengths
- scientific article; zbMATH DE number 4177081 (Why is no real title available?)
- Graphs with the Circuit Cover Property
- Generation and properties of snarks
- Circuit double covers of graphs
- Homomorphisms of Cayley graphs and cycle double covers
- On d-dimensional nowhere-zero r-flows on a graph
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)