Vertex Colorings and the Chromatic Number of Graphs | Graph Theory
Vložit
- čas přidán 15. 08. 2020
- What is a proper vertex coloring of a graph? We'll be introducing graph colorings with examples and related definitions in today's graph theory video lesson!
A proper coloring (or just: coloring) of a graph, G, is an assignment of colors (or, more generally, labels) to the vertices of G such that adjacent vertices have different colors (or labels). Consider bipartite graphs for example. If we color all vertices in one partite set blue, and all vertices in the other partite set red, we will have a proper coloring of the graph. None of the red vertices will be adjacent since they're all in a partite set, and similarly for the blue vertices. Furthermore, this means all adjacent vertices will belong to different partite sets and thus have different colors.
The minimum number of colors that a graph G can be colored with is called the chromatic number of the graph, and is denoted χ(G) [this is the greek letter chi, pronounced "kai"]. If χ(G)=k, then G is said to be k-chromatic. If G can be colored with k colors (certainly k is greater than or equal to χ(G)) then G is said to be k-colorable.
A coloring of a graph G using k vertices is called a k-coloring, and if k=χ(G) then it is a minimum coloring, as it uses the minimum possible number of colors. Note that in practice, we often use positive integers (1, 2, 3, ...) to denote our colors. This is far easier than coming up with and using arbitrarily large lists of colors.
Note that every graph of order n can be colored with n colors, since if every vertex has a different color then adjacent vertices will necessarily have different colors. Hence, χ(G) is less than or equal to the order of G.
Chromatic Number of Complete Graphs: • Chromatic Number of Co...
◆ Donate on PayPal: www.paypal.me/wrathofmath
◆ Support Wrath of Math on Patreon: / wrathofmathlessons
I hope you find this video helpful, and be sure to ask any questions down in the comments!
********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.
Vallow Bandcamp: vallow.bandcamp.com/
Vallow Spotify: open.spotify.com/artist/0fRtu...
Vallow SoundCloud: / benwatts-3
********************************************************************
+WRATH OF MATH+
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / seanemusic
![[Discrete Mathematics] Graph Coloring and Chromatic Polynomials](http://i.ytimg.com/vi/J7g5HMZgKMU/mqdefault.jpg)
Consider supporting me on Patreon to help me make more Graph Theory lessons! www.patreon.com/join/wrathofmathlessons
You will also get early access to new videos before they're published!
NOTE: At 6:30 I describe what it means for a graph to be "k-colorable". The definition I give is common, but not formal enough to avoid some possible confusion. At 7:47 I say a graph cannot be k-colorable for k greater than its number of vertices, since k colors could not be used in a coloring - there simply aren't enough vertices to accommodate k colors if k is greater than the number of vertices. However, this "upper bound" is not common in the usage of the term "k-colorable". Especially as we move on to discussing chromatic polynomials.
Often it may be convenient to say a graph is k-colorable for ANY integer greater than equal to its chromatic number. So while a complete graph on 3 vertices has chromatic number 3, for example, we could say it is k-colorable for any number greater than or equal to 3. Even though we couldn't color it with 10 distinct colors, a set of 10 colors would be sufficient (we just wouldn't use them all), so we may say it is 10-colorable anyways. Always make sure you understand the definitions being used, and I apologize if this causes any confusion!
Wonderful video man, thank you. Great explanations, thorough but not too dense, you are easy to understand.
So glad it was helpful, thanks for watching! If you're looking for more graph theory, check out my playlist and let me know if you ever have any questions! czcams.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Hi, I'm from Italy and your videos about discrete mathematics are very helpful, thank you!
Thanks for watching and I am so glad to hear they have been helpful! Let me know if you ever have any video requests!
@@WrathofMath Can you do a video about the inclusion-exclusion principle?
good, clear explanation.thanks
Can you also give explanation for how to prove that a graph cannot be colored with less that k colors?
Thanks a lot ! So well explained !
My pleasure, thanks for watching! Let me know if you ever have any video requests, and if you're looking for more graph theory - check out my playlist! czcams.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Thank u so much! I finished my activity in 3 min after watching your vid. U the best
So glad it helped! Thanks for watching and check out my playlist if you're looking for more graph theory! czcams.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Thanks a lot you really explained wonderfully so easy to understand.
Awesome, thanks for watching!
Thank you so much for this wonderful explanation! Graph coloring appears vague to me in lectures. Thanks to your explanation, I have a much clear idea of it and better prepare for my coming discrete mathematics final exam! 🙂
So glad it helped! Good luck on the final!
Hello! Thank you once again for your amazing videos & explanations! Here I am, struggling with two other Graph Theory problems & I was hoping you could enlighten me 😅
First one: show that a planar graph of order n > 2 ( n = number of vertices) contains no more than 3n - 6 edges.
Second one: G is an undirected graph of order n. Show that 𝜒(𝐺)𝜒(𝐺̅) ≤ (𝑛 + 1)^2 / 4. ( 𝜒(𝐺) - the chromatic number of the graph, 𝜒(𝐺̅) - the chromatic number of the complement graph, n - the number of vertices).
Thank you in advance, have a lovely day!
Thanks for your support, Patricia! I am glad you have found the videos helpful! Here is a proof of the first result: czcams.com/video/3LYb3k-Huoo/video.html
As for the second result, I will add it to my list of things to do! I'd give you a hint here but I don't recognize it at first glance, would have to think about it a bit!
@@WrathofMath Thank you so, so much! Have a good day!
Thanks for the gift Sean
Thank you for making this
You're very welcome, thanks a lot for watching and let me know if you ever have any questions!
So well explained
Very helpful 😍👍
Glad it was helpful!
Tq for explaining it so well❣️❣️🙏
My pleasure, thanks for watching!
Hello,
Do any one know answer for "Does there exist a 3-edge colourable graph with 10 vertices and 20 edges ?"
hi everybody, is there a video about interval graphs?
make a video on WAGNER theorem and line graphs
also show line graph of a cycle is a cycle
Awesome. Thanks a ton.
My pleasure, thanks for watching and check out my graph theory playlist if you're looking for more! Let me know if you ever have any requests.
czcams.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Hello, how many chromatic number of (c7) power 2 ????
Hey shawn, can i ask, what software are you using to do all of this? Is it OBS on a computer, or are you capturing on the ipad itself?
Im pretty sure it's all on his iPad which he is screen recording.
Please could you do a video on how to do this?
For each positive integer n prove by induction that a graph G of chromatic number n contains Kn as a subgraph
I already responded to your other comment on this topic, but I'm going to comment here as well just for other viewers who may read your comment.
The result is not true as stated, a graph of chromatic number n does not have to contain a Kn subgraph. Here is the lesson on the topic: czcams.com/video/asfhdFJaGQQ/video.html
Thank you so much!!!
No problem, thank you for watching! Check out my Graph Theory playlist if you're looking for more graph theory lessons, many more to come! czcams.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
THANK YOU!!!😄😊
My pleasure! Thank you for watching! 😊
Thank you idol!
how about the point that dont connect to any other point? what should i color it? a different color that no point got it? or same as any point color?
Generally the idea is to use as few colors as possible, so you'd probably want to use a color you'd already used for another point.
i think, now im ready to my D.math final exam, ty!
Good luck!
How'd the final go?
@@PunmasterSTP i got 80 :DD
@@ZeroTwo00002 Way to go!
can you please make a video about list coloring
Does someone know the outro song of this video? The musician is called vallow but i can not find the song...
Always happy to get more people into his music! He can be hard to follow because he keeps changing his name. He goes by Crayon Angel now: crayonangel.bandcamp.com/track/hugging-a-ghost-2
Thanks
Thank u!
Glad to help!
Thank god I found you
Do lecture on how to calculate the chromatic number for a graph
It would be more interesting!
Could you please do a video on what is math and what are the things we can do with the help of math?
That's pretty general. Did you have anything more specific in mind?
In the words of the great Calvin Harris, "Get some colours on!"
at time 5:45 i think you can do it with 3 colors
Please upload a video about edge colouring
Thanks for watching and for the request! I just recorded the edge coloring lesson, as long as there are no big problems editing - it will be up tomorrow!
@@WrathofMath thank you for your response
👍👍👍👍
Thanks Andy! Many more videos on chromatic numbers and similar topics are coming, let me know if you ever have any requests!
Ik1w09
i see orange red red
I'm not 5 years old