Vertex Colorings and the Chromatic Number of Graphs | Graph Theory
Вставка
- Опубліковано 15 жов 2024
- 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/...
◆ 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.bandcam...
Vallow Spotify: open.spotify.c...
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](/img/n.gif)
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!
Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions!
ua-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin
Graph Theory course: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Graph Theory exercises: ua-cam.com/play/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L.html
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! ua-cam.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?
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: ua-cam.com/video/3LYb3k-Huoo/v-deo.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!
Can you also give explanation for how to prove that a graph cannot be colored with less that k colors?
This is a np-complete problem, you will have to use assignment permutations and check if proper colouring is valid on given graph or not.
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!
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! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Thanks a lot you really explained wonderfully so easy to understand.
Awesome, thanks for watching!
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!
Thanks for the gift Sean
Hello,
Do any one know answer for "Does there exist a 3-edge colourable graph with 10 vertices and 20 edges ?"
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.
make a video on WAGNER theorem and line graphs
also show line graph of a cycle is a cycle
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.
Hello, how many chromatic number of (c7) power 2 ????
So well explained
Very helpful 😍👍
Glad it was helpful!
good, clear explanation.thanks
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 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! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
hi everybody, is there a video about interval graphs?
Thank you for making this
You're very welcome, thanks a lot for watching and let me know if you ever have any questions!
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: ua-cam.com/video/asfhdFJaGQQ/v-deo.html
can you please make a video about list coloring
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?
Do lecture on how to calculate the chromatic number for a graph
It would be more interesting!
Tq for explaining it so well❣️❣️🙏
My pleasure, thanks for watching!
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.
ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
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
Thank god I found you
THANK YOU!!!😄😊
My pleasure! Thank you for watching! 😊
Thank you idol!
Thank u!
Glad to help!
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! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Thanks
In the words of the great Calvin Harris, "Get some colours on!"
👍👍👍👍
Thanks Andy! Many more videos on chromatic numbers and similar topics are coming, let me know if you ever have any requests!
i see orange red red
I'm not 5 years old
Ik1w09