Skip to main content
5 of 5
added 187 characters in body

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

enter image description here

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)

enter image description 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}$