Four color theorem: recap

Recap (some facts about maps and coloring):

  • All regular maps (3-regular planar graphs) can be topologically transformed (represented) as circular or rectangular maps
  • In searching for a solution of the four color problem, it is possible to exclude maps with faces that have less then five neighbours
  • Simplified maps (no faces with less than five neighbours) of 13 faces do not exist!
  • The nunber of proper colorings (not considering permulations of colors) can be count using the “Chromatic polynomial” and dividing the result by 4! (factorial that counts the permutations). Chromatic polynomial is only known for few types of graphs (Triangle K3, Complete graph Kn, Petersen graph, …)
  • Dual graphs derived from maps can be arranged with vertices positioned on a grid (see “Rectangular grid drawings of plane graphs” by Md. Saidur Rahman, Shin-ichi Nakano, Takao Nishizeki)

To implement on the Java application (


About stefanutti

V: "Do you know me?" S: "yes." V: "No you don't." S: "Okay." V: "Did you see my picture in the paper?" S: "Yes." V: "No you didn't." S: "I don't even get the paper."
This entry was posted in Uncategorized and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s