Discrete Math II - 10.8.1 Graph Coloring

Estimated read time: 1:20

Summary

In this video, Kimberly Brehm dives into graph coloring concepts, which involves determining the minimum number of colors needed to color a graph so no two adjacent vertices share the same color. Using a fictional map, she elaborates on the chromatic number and chromatic polynomial, illustrating these concepts with several examples including bipartite graphs and cycle graphs. The lesson highlights how to calculate the number of ways to color a graph when given a certain number of colors.

Highlights

Using a fictional continent, the concept of graph coloring explains how neighboring regions require different colors 🎨.
The chromatic number of a graph means finding the minimum color count to ensure no two adjacent vertices share the same color 💡.
In bipartite graphs, only two colors are needed, while complete graphs require colors equal to the number of vertices 🔄.
Cycle graphs behave differently; even-numbered cycles need 2 colors, while odd-numbered cycles need 3 🎢.
The chromatic polynomial offers a way to calculate the distinct colorings possible when given a set number of colors 📊.
Graph enumeration principles involve determining all the possible colorings using specified color counts 🌟.
Practical exercises involve calculating colors and chromatic numbers on example graphs explained in the video 🧮.

Key Takeaways

Graph coloring helps assign colors to vertices of a graph ensuring no two adjacent vertices share the same color 🎨.
The chromatic number is the minimum number of colors needed to color a graph, represented by χ(g) 🔢.
For bipartite graphs, the chromatic number is always 2 🌈.
Complete graphs require a chromatic number equal to the number of vertices forming the graph ✨.
The chromatic polynomial helps determine the number of ways a graph can be colored given a specific number of colors 🌟.
Odd and even cycle graphs have chromatic numbers of 3 and 2, respectively 📏.
With λ colors, the graph coloring involves reducing options for each adjacent vertex 📉.

Overview

Graph coloring involves assigning colors to the vertices of a graph so that no two adjacent vertices have the same color. This concept is crucial in various applications like scheduling and map coloring. The goal is to use the fewest number of colors possible, termed as the chromatic number.

The video delves into examples using bipartite graphs, where only two colors are needed, and complete graphs which require a chromatic number equal to the number of vertices. Additionally, cycle graphs demonstrate that even cycles need two colors while odd cycles need three, showcasing the variability in coloring approaches.

To further explore graph coloring, the chromatic polynomial is introduced as a means to calculate the number of color combinations possible given a certain number of colors. This polynomial is pivotal in evaluating the enumerative aspect of graph coloring, extending beyond merely determining the chromatic number.

Chapters

00:00 - 01:30: Introduction to Graph Coloring In this chapter, we explore the concept of graph coloring using a fictitious map divided into several countries. The challenge is that neighboring countries, which do not get along, should not have the same flag color. Additionally, the flag maker aims to minimize costs by using the fewest colors possible. The chapter discusses strategies for determining the necessary number of colors, starting with a basic example.
01:30 - 03:00: Dual Graph Representation The chapter "Dual Graph Representation" explains the constraints of graph coloring, focusing on which color can be used for different nodes in a graph. For example, node 'b' cannot be colored yellow because it is adjacent to 'a', and similarly, node 'c' is also connected to 'a' and cannot use the same color. However, node 'd' can be colored yellow because it is not touching 'a'. Node 'e', being next to 'd' which is yellow, cannot use yellow, demonstrating how color choice propagates through a graph. The chapter illustrates a basic scenario where these graph coloring rules apply, and ends with the decision of coloring node 'b' with green, but raising a conflict in coloring node 'c'.
03:00 - 05:00: Chromatic Number and Complete Graphs The chapter explores the concept of chromatic number in graph theory, specifically in relation to complete graphs. It examines a scenario where a node (e) cannot be colored the same as its adjacent nodes (b, c, d) due to color conflicts. A method to assign a new color (blue) to node c is discussed, while node e requires yet another unique color. The overarching question addressed is determining the minimum number of colors needed for this graph arrangement.
05:00 - 08:00: Cycle Graphs and Generalization This chapter introduces the concept of cycle graphs and their generalizations in graph theory. A dual graph is explained where regions are considered as vertices, and connections are made based on adjacency. In the example, region A is adjacent to both B and C, and region B is adjacent to C. The dual graph helps in visualizing these relationships.
08:00 - 15:00: Chromatic Polynomial The chapter titled 'Chromatic Polynomial' discusses the concept of graph coloring, specifically focusing on how to determine the minimum number of colors required to color a graph. In this context, nodes that are adjacent (or touching) cannot share the same color. The section references an example where nodes e, c, and d are adjacent to each other in various combinations, representing a real-world map scenario. The text highlights the importance of applying graph coloring techniques to determine color distribution.

Discrete Math II - 10.8.1 Graph Coloring Transcription

00:00 - 00:30 in this video we're going to learn about graph coloring let's say we have a map of a fictitious continent divided into several countries and neighboring countries don't get along and they don't want their flags to be the same color and of course the flag maker wants to reduce costs so wants to use as few colors as possible how can we determine the number of colors necessary so obviously one thing we could do is just to look at the map and say if let's say a used yellow
00:30 - 01:00 well then b could not use yellow because b is adjacent or right next to a and c is also touching a and therefore cannot use yellow but d could use yellow because it's not touching a but obviously e could not use yellow because now it's touching d which is yellow and then i would choose another color and say b well b can be green but i can't color c green because c is
01:00 - 01:30 touching b and i can't color e green because e is touching b so now i have to find a new color let's say blue so i could say c is blue but again i can't use green or blue or yellow to color e because all three sections of b and c and d all touch e so that means e has to be a separate color so the question is what's the minimum number of colors required in this case
01:30 - 02:00 that number is four now another way to look at this question is to look at a dual graph and a dual graph just means i'm going to take the vertices i'm going to take the regions and make them vertices and then i'm going to connect these any time that the countries are adjacent so a was adjacent to b and to c and b was adjacent to c
02:00 - 02:30 and to e and c was adjacent to d and e and d was adjacent to e so this represents exactly what is shown on the map and again now we can use that same graph coloring technique remember when we're using graph coloring we're saying that we're looking for the minimum number of ways to color a graph where each node that is or each vertice that is touching cannot
02:30 - 03:00 be the same color so just as i did before if i made a yellow i couldn't make b or c yellow but i can make d yellow and then if i make b green i can't make c or e green because they both touch b they're both adjacent to b and so c could be blue but again i can't make e blue so e must be purple so really it's the same thing but obviously it's using a
03:00 - 03:30 graph instead which is much easier you might be thinking right about now that we've already learned about graph coloring which is partially true we did talk a little bit about graph coloring back when we talked about bipartite graphs and we said if i could take a graph and i could redraw it so that there were only two colors on the graph so for c6 as i have here i could redraw this with i could color this with two colors and
03:30 - 04:00 therefore i could redraw this as a bipartite graph where a and c and e were in one by partition and b and d and f were in the other partition because a was connected to b b to c c to d d to e e to f and f back to a so obviously this is a bipartite graph because a c and e
04:00 - 04:30 are not connected and b d and f are not connected the same way i could look at a b c and say if a is yellow b or c can't be yellow if b is blue c can't be blue so this one was obviously a three color graph and therefore cannot be a bipartite graph we have a special name for the minimum number of colors required to color the vertices of a graph and that is a chromatic number it's denoted by chi
04:30 - 05:00 of g and again g represents just the graph so therefore chi of g for any bipartite graph is going to be 2 because there are going to be just two colors let's take a look at the complete graphs so we have a complete graph k2 k3 k4 remember that means there are 2 3 and 4 vertices and then each vertex is connected to each other vertex so let's
05:00 - 05:30 find the chromatic number for each of those and see if we can generalize so if i look at k2 i just have two vertices obviously they're connected to each other so those both have to be different colors so the chromatic number for this graph is 2 and this is obviously k2 for k3 i could have a one color but b is connected to a and so it has to
05:30 - 06:00 be a different color and c is connected to both a and b so that has to be a different color so again that chromatic number is going to be three and we can see probably very clearly that the same is going to hold true for any complete graph so if here is a k4 complete graph then the chromatic number is four and the
06:00 - 06:30 reason for that is of course every vertex is connected to every other vertex because it is a complete graph so what can i say about k n that the chromatic number for k n is going to just be n how about for a cycle graph remember a cycle graph is a graph where each vertex is connected to the next vertex in a cycle
06:30 - 07:00 and it goes all the way back to the beginning so if i want to find the chromatic number for c3 c4 c5 and c6 and then i want to generalize for cn if i look at this first one and again we've already actually looked at this first one because c3 is also k3 because it's a complete graph where each vertex is connected to every other vertex so if i look at this one i can see that there are three colors
07:00 - 07:30 so the chromatic number here for c3 is three well let's look at c4 so this is c4 i could have one color for a i would have to have a different color for b but c could actually be blue again because c is not connected to a and d could actually be yellow again because it is not connected to b so the chromatic number
07:30 - 08:00 for c4 is just two looking at c5 again i could have a let a color for a and for c but i couldn't use that for b or d and i couldn't use it for e because e is connected to a so now i'd have to have a different color for b which i could also use for d but again i'd have to have that third color for e because it's connected to both a
08:00 - 08:30 yellow and a blue so for c5 my chromatic number is three last one and then we'll generalize i could use a color for a and for c and for e because none are connected to one another and then i could use a different color for b d f now again we've already looked at this one because this was what we said could be a bipartite graph so the chromatic number for c 6
08:30 - 09:00 is 2. so can i generalize this well it certainly appears that if i have an even number of vertices that i can split them into two and that has certainly shown true on these two examples but if i have an odd number of vertices so to generalize the chromatic number for c for an even is going to be two but looking at the odds i have that one
09:00 - 09:30 extra vertices or one extra vertex that is connected to one of each color so the chromatic number for a cycle graph that is odd is going to be 3. i want to change the question just a little bit and this in fact is not covered in your textbook in fact the next two videos are also not covered in your textbook but i think it's an important concept to talk about when we're talking about graphs
09:30 - 10:00 so i want to continue talking about not just the chromatic number but the chromatic polynomial so instead of determining the minimum number of colors necessary which is the chromatic number i now want to know the number of ways i can color a graph given a certain number of colors denoted by lambda so i'm looking back at the same dual graph that we created for our fictitious continent and before we just started by coloring a graph
10:00 - 10:30 well what i want to do now is say if i have lambda colors how many colors could i use to color a well i could use lambda colors for a how many could i use for b well i could use any color except for whatever i just used for a so that's lambda minus 1. so again we're talking about enumeration or the number of different ways now for c c is connected to both a and b so that
10:30 - 11:00 would be lambda minus 2 because i can't reuse the color for a or the color for b for d right now i only have just one color here at c so that's lambda minus 1. but for e e is connected to b and c and d so this guy would be lambda minus three because i cannot duplicate any of those colors so that tells me that the chromatic polynomial
11:00 - 11:30 is written just like this now don't worry you don't have to multiply that out i mean you certainly could but it would be kind of a fool's errand the way that we would use this then is in answering a question like how many ways can i color this graph using five colors so how could i do that all i'm going to do is replace lambda with five which means this first lambda is now five
11:30 - 12:00 lambda minus one is now four lambda minus two is three lambda minus one is four and lambda minus 3 is 2 and then i would just multiply all of those together so 5 times 4 is 20 times 3 is 60 60 times 4 is 240 240 times 2 is 480 ways that i could color if i have five
12:00 - 12:30 colors and again why does that make sense because if i have five colors this could be any of the five colors but this could only be four of the colors because i can't choose whatever i chose for a this could be three of the colors and so on and so forth for your last question i want you to find the chromatic polynomial and the solution for p g comma 6 for the graph below so press pause try that question when
12:30 - 13:00 you're ready press play to see how you did so again when we get started we would simply start with one of the vertices and label it with lambda because i can use lambda different colors for b i could use anything except for what i chose for a so that's lambda minus 1 for c i can use anything except for what i chose for b because it's not connected to a so that's lambda minus 2. and for d i could use
13:00 - 13:30 only lambda minus 3 because d is connected to a b and c and so it must be different than each of those so i have lambda lambda minus 1 lambda minus 2 and lambda minus 3. so what is my solution my solution asks me to find when the number of colors i have is six so if they wanted the chromatic polynomial oops
13:30 - 14:00 then i would keep lambda as a general value so that would be lambda lambda minus one lambda minus two lambda minus three but if i'm actually using it for the value of six i'm just going to replace lambda with six so six times five times four times three and so i would get 30 times four 120
14:00 - 14:30 times 3 360. up next we are going to deviate from the textbook just a little bit we've been talking about graphs we've been talking now about the number of graphs that i can create using a certain number of colors now what i want to do is dive a little bit into group theory so we're not going to go crazy into group theory but i do want to talk about how groups and graphs and burnside and polya can help us with
14:30 - 15:00 graph enumeration