Map coloring. The four-color theorem

Niniejsza praca magisterska podejmuje problematykę kolorowania map. Zagadnienie to jest częścią szerzej pojętego kolorowania grafów, które należy do dziedziny, jaką jest teoria grafów. Najważniejszym twierdzeniem przedstawianego problemu jest twierdzenie o czterech barwach, którego powstanie przypada na XIX wiek i jest przypisywane Francisowi Guthrie. Na przestrzeni ostatnich 150 lat wielu matematyków zajmowało się problemem kolorowania map. Dzięki temu powstało wiele istotnych twierdzeń. Celem pracy jest przedstawienie rozwoju problematyki kolorowania map na przestrzeni lat. Szczególny nacisk został położony na zagadnienie czterech barw. Oprócz opisu historycznego postępu w tej dziedzinie praca zawiera wiele twierdzeń związanych z problematyką kolorowania map wraz z dowodami. W celu lepszego przedstawienia problemu część przedstawianych kwestii zilustrowana została licznymi grafikami. Niniejsza praca została podzielona na cztery rozdziały. Pierwszy z nich zawiera opis historyczny rozwoju problemu na przestrzeni lat. Można znaleźć w nim biografię inicjatora problemu czterech barw Francisa Guthrie. Część ta zajmuje się głównie przedstawieniem, w jaki sposób zagadnienie czterech barw było rozwijane przez kolejnych matematyków. Najgłówniejszą kwestią poruszanego tematu jest problematyka związana z dowodem twierdzenia o czterech kolorach. W tym rozdziale przedstawione zostają kolejne postacie oraz ich próby udowodnienia poruszanego faktu. Kolejny rozdział zawiera podstawowe definicje oraz oznaczenia związane z kolorowaniem grafów. W następnej części czytelnik zapoznaje się z twierdzeniami dotyczącymi kolorowania grafów, w tym również map, przy użyciu dwóch bądź trzech barw. Wszystkie te twierdzenia powstawały podczas zajmowania się tematyką czterech barw przez różnych matematyków. Ostatni rozdział dotyczy głównie twierdzenia o czterech barwach. Są w nim przedstawione narzędzia użyte do pierwszego dowodu, który stworzył Alfred Kempe. Pokazany jest również sam dowód oraz kontrprzykład obalający jego prawdziwość. W dalszej części ukazana jest kolejna próba udowodnia poruszanej kwestii. Czwarty rozdział zawiera również inne twierdzenia związane z problematyką kolorowania grafów za pomocą czterech barw.

This master's dissertation is about the map coloring. This problem is the part of the graph coloring that belongs to graph theory. The main theorem of the issue that is consider is the four-color theorem. It was initiated by Francis Guthrie in XIX century. Over the 150 years lots of mathematicians dealt with map coloring. Due to this fact we have many interesting and important theorems that refer to graph coloring. The main aim of this dissertation is to show how the problem of map coloring progressed. It contains historical description and many theorems with proof. Some part of the issues that are consider is illustrated for better presentation of the problem. This dissertation is divided into four chapters. First is about the historical progress. The biography of the Francis Guthrie that was the initiator of the four-color theorem can be found there. This part mainly is about the four-color theorem and attempts to prove it. Next chapter contains definitions and symbols that are connected with map coloring. In next part theorems about 2-coloring and 3-coloring of the maps can be found. Last chapter is mainly about the four-color theorem. Tools that were used by Alfred Kempe to prove this theorem appeared there. The proof of the Alfred Kempe and counterexample are shown there. In this part there are other theorems connected with 4-coloring of the map too.