Return to Answer

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

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

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.

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

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 easy 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 $d-1$. But given the graphs above, the value of $d=\min\{\deg(v),\deg(v)>4\}$ over all maximal planar graphs is unbounded.

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.