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.sstatic.net/d8v3i.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.sstatic.net/mjwYq.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.
Best Answer
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