An inequality on the number of vertex colorings of planar graphs

Question

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).

Answer 1

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}$