Here is an example of the steps to take to use the 4ct algorithm on Voronoi diagrams. four-color-theorem.org/2022/09/04/color-voronoi-graphs

I forgot about one thing. The graph has to be 3-regular for my algorithm to work. Voronoi are not :-(. For the study of the four-color theorem, this is a standard limitation

Hi @ReZhacai. If you need help with this github.com/stefanutti/maps-coloring-python I can help. Fastest way to have the four coloring of the graph is to prepare a file with a planar representation of the graph (I can give info about it). This is because if you start from any other representation (.edgelist or .dot) when you load the file it has to verify the graph is planar using the sage function, which is slow. Or if you can send me the graph in a standard format I can return it to you colored.

@ReZhacai About the error "ModuleNotFoundError: No module named 'sage_numerical_backends_gurobi'" I found this: pypi.org/project/sage-numerical-backends-gurobi. When you say you generated the graph "from an actual shapefile" what do you mean?

The graph must be 3-regular for my case. Can you share the my.edgelist file?

Never saw that problem before. Did you use my code or something else?

About the comment to tramsform the graph to cubic, here is an example 4coloring.files.wordpress.com/2019/01/kempe-cubic.png of a vertex with more than 3 edges that can be transformed

about the real map you want to color do you have a graph representation of it or just the printed map?

To tramsform the graph to cubic, consider a vertex that has more than 3 edge and make a small circle that has the vertex as the center and remove all edges inside the circle. If you do that four all vertex that have more than 3 edges. At the end you will have a cubic graph. If you can color this, just shrink down to a point all circles that were added

About Sage I am planning to remove this dependemcy and use networkx instead. Can you also share the link to the Sage+Gurobi algorithm, I would like to try it. Thanks in advance.

Considering only cubic graphs is the standard approach four maps. From Wikipedia: Kempe's argument goes as follows. First, if planar regions separated by the graph are not triangulated, i.e. do not have exactly three edges in their boundaries, we can add edges without introducing new vertices in order to make every region triangular, including the unbounded outer region. If this triangulated graph is colorable using four colors or fewer, so is the original graph since the same coloring is valid if edges are removed. So it suffices to prove the four color theorem for triangulated graphs to prov