{'fraction_non_alphanumeric': 0.026944971537001896, 'fraction_numerical': 0.014990512333965844, 'mean_word_length': 4.565997888067582, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Graph Coloring : History , results and open problems

Coloring theory started with the problem of coloring the countries of a map in such a way that no two countries that have a common border receive the same color. If we denote the countries by points in the plane and connect each pair of points that correspond to countries with a common border by a curve, we obtain a planar graph. The celebrated Four Color Problem asks if every planar graph can be colored with 4 colors. It seems to have been mentioned for the first time in writing in an 1852 letter from A. De Morgan to W.R. Hamilton. Nobody thought at that time that it was the beginning of a new theory. The first ”proof” was given by Kempe in 1879. It stood for more than 10 years until Heawood in 1890 found a mistake. Heawood proved that five colors are enough to color any map. The Four Color Problem became one of the most difficult problems in Graph Theory. Besides colorings it stimulated many other areas of graph theory. Generally, coloring theory is the theory about conflicts: adjacent vertices in a graph always must have distinct colors, i.e. they are in a permanent conflict. If we have a ”good” coloring, then we respect all the conflicts. If we have a ”bad” coloring, then we have a pair of adjacent vertices colored with the same color. This looks like having a geographic map where some two countries having common border are colored with the same color. Graphs are used to depict ”what is in conflict with what”, and colors are used to denote the state of a vertex. So, more precisely, coloring theory is the theory of ”partitioning the sets having internal unreconcilable conflicts” because we will only count ”good” colorings. The most famous erroneous proof was very instructive. On one hand, it shows an excellent example how drawings may be used in Graph Theory proofs. On the other hand, it explicitly exhibits the limits of drawings. Since the result was considered proven until 1890, it also demonstrated the fact that mathematicians of those times (like nowadays) liked writing papers MORE than reading them. But on the top of all that, nobody could even imagine what a dramatic history was ahead. Formulated first in 1852 by Francis Guthrie (a student (!) of de Morgan), ”proved” in 1879 by Kempe, refuted in 1890 by Heawod, the Four Color Problem became one of the most famous problems in Discrete Mathematics in 20th century before in 1977 it became the Four Color Theorem by Appel, Haken, and Koch. Besides many erroneous proofs (not only that by Kempe), it generated many new directions in Graph Theory. For example, only one sub-direction of chromatic polynomials introduced by Birkhoff in 1912 with the aim to solve the problem by algebraic methods counts more than 500 research papers. The main idea of the final proof is quite simple by induction on the number of vertices; but the number of cases is huge. Though the Kempe’s proof was erroneous, his idea of alternating paths and further re-coloring of the respective subgraphs was used in the final proof. A path on which two colors alternate is called a Kempe chain. In a plane triangulation, a configuration is a derived subgraph with respect to a separating cycle; it is a subgraph induced by the cycle and all the vertices which are inside the cycle in the plane. There were the following two basic steps in the proof: 1. Proof that any plane triangulation contains a configuration from a list of unavoidable configurations. 2. Proof that each unavoidable configuration is reducible. In 1976, Appel, Haken, and Koch, using 1200 hours of computer time, found 1936 (!) unavoidable configurations and proved that all they are reducible. Historically, it was the first time when a famous mathematical problem was solved by extensive use of computers. The final accord in this one-century drama occured when the result was widely announced, the paper was published in 1977, and the University of Illinois even announced it by postage meter stamp of ”four colors suffice”, a few errors were found in the original proof(!). Fortunately for the authors, they have been fixed. For the first time, regardless the fact that there is no human being who would check the entire proof (because it contains steps that most likely can never be verified by humans), the problem is considered completely solved. In 1996, Robertson, Sanders, Seymour and Thomas improved the proof by finding the set of only (!) 633 reducible configurations. Computers, Kempe chains, and some other techniques were used in both proofs. The three consecutive theorems Theorem about six colors, Theorem about five colors and Theorem about four colors show the main feature of graph coloring: there is a very simple proof for six colors, a relatively simple proof for five colors and an incredible difficult and complex proof for four colors. Thus, the Four Color Problem, formulated by a student, was first ”solved” by a lawyer, and really solved with many contributions of the very prominent mathematicians of the century. Let us imagine year 1912. Just 63 years passed since in 1849 Gauss published his second proof of the fundamental theorem of algebra, saying that every polynomial of degree n with complex coefficients has precisely n roots. Though the