10.8 Graph Coloring Flashcards
Dual graph of a map :
Each map in the plane can be represented by a graph. To set up this correspondence, each
region of the map is represented by a vertex. Edges connect two vertices if the regions represented by these vertices have a common border. Two regions that touch at only one point are
not considered adjacent. The resulting graph is called the dual graph of the map. By the way
in which dual graphs of maps are constructed, it is clear that any map in the plane has a planar
dual graph.
Graph coloring :
definition 1:
A coloring of a simple graph is the assignment of a color to each vertex of the graph so that
no two adjacent vertices are assigned the same color.
Definition 2:
Chromatic number:
The chromatic number of a graph is the least number of colors needed for a coloring of
this graph. The chromatic number of a graph G is denoted by 𝜒(G). (Here 𝜒 is the Greek
letter chi.)
Theorem 1:
THE FOUR COLOR THEOREM
proof?
The chromatic number of a planar graph is no greater
than four.
Many false were given, finally one using computers, it does case by case analysis.
They showed that if the four color theorem were false, there would have to be a counterexample of one of approximately 2000 different types, and they then showed that none of these types exists.
Show that chromatic number of graph is k:
Two things are required:
1: we must
show that the graph can be colored with k colors. This can be done by constructing such a
coloring.
2: We must show that the graph cannot be colored using fewer than k colors.
chromatic number of Kn ?
𝜒(Kn) = n.
e chromatic number of the complete bipartite graph Km,n :
2
What is the chromatic number of the graph Cn, where n ≥ 3
In general, two colors are needed to color Cn when n is even. To construct such a coloring,
simply pick a vertex and color it red. Proceed around the graph in a clockwise direction (using a planar representation of the graph) coloring the second vertex blue, the third vertex red,
and so on. The nth vertex can be colored blue, because the two vertices adjacent to it, namely
the(n − 1)st and the first vertices, are both colored red.
When n is odd and n > 1, the chromatic number of Cn is 3. To see this, pick an initial vertex.
To use only two colors, it is necessary to alternate colors as the graph is traversed in a clockwise
direction. However, the nth vertex reached is adjacent to two vertices of different colors, namely,
the first and (n − 1)st. Hence, a third color must be used.
𝜒(Cn) = 2 if n is an even positive integer with n ≥ 4 and 𝜒(Cn) = 3 if n is an odd positive integer with n ≥ 3.
Algorithm to find Chromatic number of graph :
- exponential Links worst-case time complexity (in the number of vertices of the graph).
- even approximation is difficult.
It has been shown that if
there were an algorithm with polynomial worst-case time complexity that could approximate
the chromatic number of a graph up to a factor of 2 (that is, construct a bound that was no
more than double the chromatic number of the graph), then an algorithm with polynomial worstcase time complexity for finding the chromatic number of the graph would also exist.
Applications of Graph Colorings
- Scheduling
- Frequency Assignments
- Index Registers
Scheduling final exams :
How can the final exams at a university be scheduled so that no
student has two exams at the same time?
This scheduling problem can be solved using a graph model, with vertices representing
courses and with an edge between two vertices if there is a common student in the courses they
represent. Each time slot for a final exam is represented by a different color. A scheduling of the
exams corresponds to a coloring of the associated graph.
Frequency Assignments
Television channels 2 through 13 are assigned to stations in North
America so that no two stations within 150 miles can operate on the same channel. How can
the assignment of channels be modeled by graph coloring?
Construct a graph by assigning a vertex to each station. Two vertices are connected
by an edge if they are located within 150 miles of each other. An assignment of channels corresponds to a coloring of the graph, where each color represents a different channel.
Index Registers
In efficient compilers the execution of loops is speeded up when frequently
used variables are stored temporarily in index registers in the central processing unit, instead
of in regular memory. For a given loop, how many index registers are needed? This problem
can be addressed using a graph coloring model. To set up the model, let each vertex of a graph
represent a variable in the loop. There is an edge between two vertices if the variables they
represent must be stored in index registers at the same time during the execution of the loop.
Thus, the chromatic number of the graph gives the number of index registers needed, because
different registers must be assigned to variables when the vertices representing these variables
are adjacent in the graph.
