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.


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.


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.


1 Answer 1


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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.