# A proper Vertex, Edge, and Face coloring of a surface Graph

Recently in my graph theory class my professor brought up the concept of Total Coloring. I was wondering have there been any theorems/work done on the concept of a coloring of edges, vertices, and faces of a graph, such that we have a total coloring of edges and vertices, a proper face coloring, no incident faces and edges share a color, and no incident faces and vertices share a coloring? What would such a coloring be called? Since complete coloring already refers to something else, I was thinking final coloring.

If we define this coloring as $$\phi(\Gamma)$$ for a graph $$\Gamma=(V,E),$$ then using the properties that a circuit $$C_n$$ has a total coloring of $$4$$ colors, we can deduce than an upper bound for biconnected planar graphs would have to be at least $$\max(\deg(x))_{x\in V}+4,$$ as we would be forced to choose $$2$$ additional colors for the outer and inner faces. I tried coloring $$K_4$$ this way, and so far I've manage to color it requiring $$7$$ colors, which is $$\max(\deg(x))_{v\in V}+4$$. Here is a link to that coloring.

https://i.imgur.com/pnMtvUU.png

Of course this image is only valid for one embedding of $$K_4.$$ I can actually show that the formula holds for other embedding of $$K_4.$$ So if $$\Gamma$$ is a planar $$K_4,$$ then $$\phi(\Gamma))\leq\max(\deg(v))_{v\in V}+4.$$

If $$\Gamma$$ is a wheels with at least $$5$$ spokes, it seems you can show algorithmically that $$\max(\deg(v))_{v\in V}+1=\phi(\Gamma)$$. Label the exterior vertices $$v_1,...,v_{n-1}$$ and the interior vertex $$v_n.$$ Then $$\max(\deg(v))_{v\in V}=\deg(v_n)=n-1.$$ Color the vertices $$v_1,...,v_n$$ with colors $$c_1,...,c_n.$$ let $$\ell(i+1)$$ denote the least residue mod $$n-1$$ of $$i+1.$$ Color $$\{v_n,v_{\ell(i+1)}\}$$ with $$c_i$$. No problems so far.

Color the edge $$\{v_{\ell(i+2)},v_{\ell(i+3)}\}$$ with $$c_i.$$ Again there are no problems, as we're working with at least $$5$$ spokes. So far we'd actually be good with $$4$$ spokes.

Now we color the face $$\{v_n,v_{\ell(i+3)},v_{\ell(i+4)}\}$$ with $$c_i.$$ Since we're working with $$5$$ spoke's we've still not gone all the way around the wheel, so we're good.

Now we're free to color the outside face $$c_n.$$ This gives a final coloring of the wheel with $$n-1$$ spokes using $$n$$ colors.

This isn't a proof, to be sure, though I could write one. To convince you that it will work without a rigorous proof consider the image below.

https://i.imgur.com/7NXvblS.png

Starting with the purple vertex we moved $$1/5$$ around the circle and color a spoke purple, move another $$1/5$$ and color an exterior edge purple, then move another $$1/5$$ and color a face purple. We've not gone far enough for our face to touch the purple vertex, so we're good. Notice that this method needs at least $$5$$ spokes, as in the linked image, if we only had $$4$$ spokes the purple vertex would be incident to the purple face.

So based on these examples I conjectured that for any biconnected planar graph we have $$\phi(\Gamma)\leq\max(\deg(v))_{v\in V}+4.$$

We know the formula holds for Wheels and Cycles. It holds for all planar embeddings of $$K_4,$$ hence since the only other biconnected planar complete graph is a circuit it holds for all planar complete graphs. I've no idea how to show it in general though.

This type of coloring is called a vertex-edge-face coloring in this paper, where the same conjecture is made: that for any planar graph $$G$$ with maximum degree $$\Delta$$, $$\chi^{vef}(G) \le \Delta + 4,$$ where $$\chi^{vef}$$ is the vertex-edge-face chromatic number. (Actually, the paper's Conjecture 1 goes further and makes this conjecture for list coloring.) Furthermore, the paper proves this when $$\Delta \ge 12$$.
There are a couple of ways to prove the weaker result that $$\chi^{vef}(G) \le \Delta + 7$$: either
1. By combining Theorem 1 of this paper (due to Borodin) that $$\chi^{vf}(G) \le 6$$ for planar graphs, with Vizing's theorem that $$\chi^e(G) \le \Delta+1$$ for all graphs, or
2. By combining Theorem 2 of this paper (due to Waller) that $$\chi^{ef}(G) \le \Delta+3$$ for planar graphs, with the four-color theorem that $$\chi^v(G) \le 4$$ for planar graphs.