I generated a planar map of 10000 nodes and then colored using the 4ct python coloring program.

It did use Tait coloring (3-edge-coloring) which is equivalent to the four face coloring of the four color theorem.

It works pretty fast using:

• graph reduction removing edges from F2, F3, F4, F5
• graph rebuilding using Kempe chain color switching techniques