5
$\begingroup$

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:

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

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

1 Answer 1

2
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 27, 2021 at 7:38
  • $\begingroup$ 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. $\endgroup$ Oct 27, 2021 at 7:44
  • 1
    $\begingroup$ No problem! I'll look at it with fresh eyes now ^^ I'll edit the answer to note that the question has been changed. $\endgroup$ Oct 27, 2021 at 7:47
  • $\begingroup$ 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. $\endgroup$ Oct 27, 2021 at 7:47
  • 1
    $\begingroup$ For information, the conjecture is true for all graph $G$ on at most 10 vertices. $\endgroup$ Oct 27, 2021 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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