Graph Coloring: A Breakthrough in Science

1
Name:
Course
Professor’s name
University name
City, State
Date of submission

2
Abstract
In graph theory, the coloring of graphs is a special case of graph marking. When coloring
the elements of a graph, labels are placed in correspondence with certain constraints; these labels
are traditionally called "colors." In the simplest case, a method of coloring the vertices of a graph
in which two adjacent vertices correspond to different colors is called the vertex color. Similarly,
the coloring of edges assigns a color to each edge so that any two adjacent edges have different
colors (Ahuja, 2017). Coloring the vertices is the main problem of coloring graphs, all other
problems in this area can be transferred to this model. For example, the coloring of edges of a
graph is the coloring of the vertices of its edge graph, and the coloring of regions of a flat graph
is the coloring of the vertices of the dual graph. Nevertheless, other problems of coloring graphs
are often put and solved in the original formulation. The reason for this is partly that this gives a
better idea of what is happening and is more indicative, and partly because some tasks are more
convenient to solve in this way (for example, the coloring of edges). It was generalized to the
coloration of regions of a flat graph. Through dual graphs, this model spread to the coloring of
vertices, and then to other types of graphs (Jupudi, and Fortinet , 2017). In the mathematical and
computer representation, usually as colors, integer non-negative numbers are used. Thus, we can
use any finite set as a "color set", and the problem of coloring graphs depends on the number of
colors, and not on what they are.
Introduction
In this research chapter, we invite the reader to think about one problem of graph theory,
which seems very simple. This is the task of coloring cards. You will see how an entertaining
task can sometimes provoke a genuine breakthrough in science.

3
Maps and colors
Most geographic maps can be interpreted as graphs whose vertices are points where three
lines meet or more, and edges - the boundaries of countries and territories. The compilers of the
maps tried to color them so that different countries and territories were painted in different
colors. Given the number of countries and the limited number of colors that were used for color
printing, it was required to color the cards so that only countries with common borders were
painted in different colors (Junior and Backes, 2014). Note that if we also want to colorize the
outer area, then we need 2, 3, 4, respectively in again 4 colors.
We use the method of proof by induction, which is that we prove this statement for n = 1 and see
if this is true for n + 1 if it is true for n.
Purposes of the assignment
For n = 1 (a), the proof is trivial. Assume that this statement is true for n lines (b), and
consider a map on which n + 1 is a straight line (c). If we delete one of the lines, we get a card of
n lines that can be colored with two colors (right by induction). Therefore, when you add (n + 1)
-th straight line above (or right) from the added line, all colors remain unchanged, and on the
other side of this line all areas will change color to the opposite one. Thus, a map of n + 1
straight can be painted with only two colors. In view of the corresponding differences, it can be
seen that any map of n circles randomly distributed on a plane can also be colored with two
colors. And in the case of straight lines, and in the case of circles, all vertices of the obtained
graph will have an even power (Leighton, 2014). In any graph whose vertices have an even
power greater than two, deleting the cycle yields a graph whose vertices will still have an even