SIT792 - Vertex Coloring in Graph Theory: Techniques and Applications

This report delves into the realm of graph theory, specifically focusing on vertex coloring techniques. It begins by defining graph coloring as a special case of graph marking, where labels, traditionally called 'colors,' are assigned to graph elements under certain constraints. The report highlights vertex coloring, where adjacent vertices receive different colors, as the primary problem in graph coloring, with other problems often reducible to this model. It touches upon the historical context, noting how edge coloring and region coloring in flat graphs relate to vertex coloring through edge graphs and dual graphs, respectively. The report further explores the application of graph coloring to geographic maps, illustrating how map coloring problems can be framed within graph theory. It discusses the theorem on two colors, proving it by induction and extending it to maps of circles. The report then examines the problem of coloring graphs with vertices of degree not exceeding 3, along with theorems on three colors and the application of graph coloring to the 'museum guard problem'. Finally, the document concludes by reflecting on the challenges in determining the sufficiency of four colors for coloring any graph, highlighting the historical context and the problem's influence on other areas of mathematics.

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

4
power. Like all graphs of this type, it can be represented in the form of lines or circles. The
theorem on two colors is proved (Malyshev and Pochinka, 2016).
Problem in research
In the case of coloring problems, in many cases, only graphs are of interest, the degree of
each vertex of which does not exceed 3. If one of the vertices of the graph has degree greater
than 3, then we can draw a circle C with center at this vertex that does not touch any other
vertex, then remove the elements of the graph inside this circle and obtain a new graph with
vertices of degree 3 corresponding to the intersections of C and the original edges (Pinedo,
2016). If we paint the resulting map, and then remove the constructed circle and return to the
original graph, the problem will be solved, as shown in the following figures. Thus, in graph
coloring problems, sometimes only flat graphs can be considered, each vertex of which has
degree 3.
The proof of the theorem on three colors is more complicated than the previous one, so
we will not give it here. The theorem itself sounds like this: A plane graph with vertices of
degree 3 can be colored in three colors if and only if However, in the case of the non-convex
polygon shown in the following figure, one guard is no longer sufficient. The answer is that for a
polygon with n sides, [n / 3] guards are sufficient. It is curious that the proof uses a graph
obtained by triangulating the museum hall (that is, dividing the polygon into triangles). The
vertices of this graph can be colored in three colors so that the adjacent vertices will be painted in
different colors (Rao and Yip, 2014). So, the signs of graphs were opened, for coloring of which
two or three colors are enough, and it soon became apparent that five colors are sufficient for
coloring any graph . However, it turned out to be very difficult to determine whether four colors

5
are sufficient for coloring any graph. In mathematics, this happened more than once: the
particular case was the most difficult (Timmons, 2015).
Conclusion
Nobody managed to find a map, for the coloring of which would require five colors.
Therefore, it was logical to assume that four colors should be enough for any card. As is often
the case in mathematics, unsuccessful attempts to solve one problem made it possible to obtain
results applicable in other areas (geometry, topology, combinatorics). It is curious that a solution
of this problem was found for maps located on irregularly shaped surfaces. For example, for a
torus (a geometrical body in the form of a donut) you need seven colors, for the Mobius strip (to
make it, you need to glue the edges of the elongated rectangle, after having unfolded one of
them) - six colors.

6
Bibliography
Ahuja, R.K., 2017. Network flows: theory, algorithms, and applications. Pearson Education.
Jupudi, S.Y. and Shanmugham, R., Fortinet Inc, 2017. Automatic channel selection in wireless
local area network (WLAN) controller based deployments using color graphs. U.S. Patent
9,743,418.
Junior, J.J.D.M.S., Cortez, P.C. and Backes, A.R., 2014. Color texture classification using
shortest paths in graphs. IEEE Transactions on Image Processing, 23(9), pp.3751-3761.
Leighton, F.T., 2014. Introduction to parallel algorithms and architectures: Arrays· trees·
hypercubes. Elsevier.
Malyshev, D. and Pochinka, O., 2016. Description of domain structures in the SolarCorona by
means multi-color graphs. Динамические системы, 6(1), pp.3-14.
Pinedo, M.L., 2016. Scheduling: theory, algorithms, and systems. Springer.
Rao, K.R. and Yip, P., 2014. Discrete cosine transform: algorithms, advantages, applications.
Academic press.
Timmons, C., 2015. Star coloring planar graphs.