Exclaves and enclaves could break the "four" conjecture.

I took your map of the USA and tried to work the Canadian provinces adjecent to the American states. I had no trouble with four colors. So maybe FOUR is the way.

But I am wondering about some of the gerrymandered congressional districts in the USA. There are a few with really weird shapes and border with 10 or more other districts. If two gerrymandered districts are adjacent, that would leave only two colors for their neighbors.

Maybe I'll get to this someday.