Said ginormous appendix is still small compared to the appendix of the original proof!
OTOH my memory of other attempts to prove the theorem suggest to me that as long as your graph doesn't have any vertices which have 5 edges meeting at it then a good algorithm might exist. This stems from the fact it is far easier to prove the 4 colour theorem for all maps without pentagonal countries :).
There exists somewhere in my house a passable (if overly verbose) pop-sci book about the theorem which neatly sets out a) how you can reduce the problem to {2,3,4,5}-agonal countries and b) how {2,3,4}-agonal countries aren't too much of a problem. I believe it is called 'Four colours suffice' or something similar.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
OTOH my memory of other attempts to prove the theorem suggest to me that as long as your graph doesn't have any vertices which have 5 edges meeting at it then a good algorithm might exist. This stems from the fact it is far easier to prove the 4 colour theorem for all maps without pentagonal countries :).
There exists somewhere in my house a passable (if overly verbose) pop-sci book about the theorem which neatly sets out a) how you can reduce the problem to {2,3,4,5}-agonal countries and b) how {2,3,4}-agonal countries aren't too much of a problem. I believe it is called 'Four colours suffice' or something similar.