# An inequality on the number of vertex colorings of planar graphs

Conjecture: Let $$G$$ be a simple maximal planar graph, and let $$P(G,4)$$ be the number of proper vertex colorings of $$G$$ with four colors. Let $$v$$ be a vertex of $$G$$ with degree $${\rm deg}(v)=5$$, and let $$G-v$$ be the graph obtained after removing that vertex from $$G$$. Then, we have $$P(G-v,4)\leq 4 P(G,4)$$, that is, the number of vertex colorings (with four colors) for $$G-v$$ is at most four times as large than for $$G$$.

Question 1: Is the above result known in the graph theory literature? Where would be a good starting point to find similar results?

Question 2: Is the conjecture true? How to prove it?

Comments: I believe the conjecture is correct based on numerical verification in many examples. The factor 4 in the inequality is sharp, that is, there exist maximal planar graphs $$G$$ with $${\rm deg}(v)=5$$ such that $$P(G-v,4) = 4 P(G,4)$$, for example:

(This example has $$P(G,4)=24$$, and after removal of either one of the degree five vertices we obtain $$P(G-v,4)=96$$.)

Notice that the truth of this conjecture implies the four-color theorem: Assume the conjecture is correct. Choose $$G$$ to be a minimal (in the sense of smallest number of vertices) counterexample to the four-color theorem. Assuming that $$G$$ is maximal planar is without loss of generality (if it is not maximal, then we just add edges until it is). If the minimal degree of $$G$$ is smaller than five, then there are well-known arguments (Kempe) to derive a contradiction. Thus, existence of $$v$$ with $${\rm deg}(v)=5$$ is without loss of generality. The conjecture then immediately delivers the result $$P(G,4)>0$$, because we have $$P(G-v,4)>0$$ (otherwise the counterexample would not be minimal).

• "four times larger" means five times as large. You want four times as large (which is three times larger). Oct 27, 2021 at 12:15
• Thank you, Gerry, I changed this to "four times as large" now. Oct 27, 2021 at 13:26

This answer had been redacted before the question was edited. It is NOT answering the current problem, it was dealing with graphs with maximum degree at least $$5$$.

I don't know about your conjecture, but it does not imply the 4CT. How do you know that your minimal counter-example contains a vertex of degree exactly $$5$$ ? It's only known that any maximal planar graph contains a vertex of degree at most $$5$$.

For example the following graph is maximal planar, with max degree $$6$$, but no vertex of degree exactly $$5$$.

Note that if you delete the vertex $$1$$, of degree $$6$$, then the number of coloring of this new graph is more than $$4$$ times the number of coloring of the original graph ($$192$$ and $$24$$ respectively).

Actually, it's rather easy to construct a maximum planar graph, on $$n$$ vertices, with degree sequence $$\{3,3,4,4,\ldots,4,n-1,n-1\}$$. Take a path on $$n-2$$ vertices $$\{1,\ldots,n-2\}$$, add a vertex $$n-1$$ "above" the path, and a vertex $$n$$ "below" the path, joint each vertex of the path to $$n-1$$ and to $$n$$, and finally add an edge $$(n-1,n)$$. For example on $$9$$ vertices (don't take into account the vertices' label here)

And I suspect that the conjecture should be feasible using some combinatorics arguments : a more general conjecture would be that if you remove a vertex of degree $$d$$, then you can only multiply the number of possible coloring by $$c(d)$$, for some constant $$c$$ depending only on $$d$$. But given the graphs above, the value of $$d=\min\{\deg(v),\deg(v)>4\}$$ over all maximal planar graphs is unbounded. So this will not imply the 4CT.

Finally, having looked at some small values, a generalized conjecture :

Let $$G$$ be a simple maximal planar graph, and let $$P(G,4)$$ be the number of proper vertex colorings of $$G$$ with four colors. Let $$v$$ be a vertex of G with degree $$\deg(v)=d>4$$, and let $$G−v$$ be the graph obtained after removing that vertex from $$G$$. Then, we have $$P(G−v,4)\leq c(d)\cdot P(G,4)$$, with $$c(d) = 2^{d-3}$$

• Thank you for your reply. Indeed, instead of writing "If the maximal degree of 𝐺 is smaller than four, ..." I should have written "If the minimal degree of $G$ is smaller than five, ..." These are not the same statements, as you point out correctly. However, the claim regarding the four-color theorem is valid. For example, if there is a degree 3 vertex in the minimal counterexample we can just remove that vertex and the resulting graph should still be a counterexample. For degrees $\leq 4$ these are the arguments by Kempe from the 19th century. Oct 27, 2021 at 7:38
• I edited the post now to stay "If the minimal degree of 𝐺 is smaller than five,..." to avoid similar confusion in the future. Sorry about this mistake. Oct 27, 2021 at 7:44
• No problem! I'll look at it with fresh eyes now ^^ I'll edit the answer to note that the question has been changed. Oct 27, 2021 at 7:47
• I like your generalization to ${\rm deg}(v)=d>4$, it looks plausible. The requirement of maximality of the graph can potentially also be relaxed. Oct 27, 2021 at 7:47
• For information, the conjecture is true for all graph $G$ on at most 10 vertices. Oct 27, 2021 at 7:52