Vertex Colorings and the Chromatic Number of Graphs | Graph Theory

[@WrathofMath]

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! kzbin.info/door/yEKvaxi8mt9FMc62MHcliwjoin Graph Theory course: kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Graph Theory exercises: kzbin.info/aero/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L

[@suprecam9880]

Wonderful video man, thank you. Great explanations, thorough but not too dense, you are easy to understand.

[@WrathofMath]

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! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@marcorossettini9232]

Hi, I'm from Italy and your videos about discrete mathematics are very helpful, thank you!

[@WrathofMath]

Thanks for watching and I am so glad to hear they have been helpful! Let me know if you ever have any video requests!

[@marcorossettini9232]

@@WrathofMath Can you do a video about the inclusion-exclusion principle?

[@sunethnarada]

I'm from srilanka, your teaching skill is amazing

[@patriciabalutel1730]

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!

[@WrathofMath]

Thanks for your support, Patricia! I am glad you have found the videos helpful! Here is a proof of the first result: kzbin.info/www/bejne/aX28k2ahYq2opdE 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!

[@patriciabalutel1730]

@@WrathofMath Thank you so, so much! Have a good day!

[@satchitnagpal7859]

Can you also give explanation for how to prove that a graph cannot be colored with less that k colors?

[@LearningCS-jp4cb]

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.

[@jingyiwang5113]

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! 🙂

[@WrathofMath]

So glad it helped! Good luck on the final!

[@Bk_official003]

Thanks a lot you really explained wonderfully so easy to understand.

[@WrathofMath]

Awesome, thanks for watching!

[@sanjosekassiels.3830]

Thank u so much! I finished my activity in 3 min after watching your vid. U the best

[@WrathofMath]

So glad it helped! Thanks for watching and check out my playlist if you're looking for more graph theory! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@EunicekateVelasco-gv7xj]

Hello, I have a question about the maximum k-colourable since the notes that my professor gave states that maximum k-colourable is k+1 but in your video it is only k. please enlighten me. I am reviewing for my finals exam. thank you

[@wishmanoor-fo7rp]

So well explained Very helpful 😍👍

[@WrathofMath]

Glad it was helpful!

[@vonage_sasb9356]

Hello, Do any one know answer for "Does there exist a 3-edge colourable graph with 10 vertices and 20 edges ?"

[@bytecode5834]

Thanks for the gift Sean

[@HamsaShehadeh]

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?

[@PunmasterSTP]

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.

[@Utkarshkharb]

Thanks a lot ! So well explained !

[@WrathofMath]

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! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@monoman4083]

good, clear explanation.thanks

[@SHASHANKRUSTAGII]

make a video on WAGNER theorem and line graphs also show line graph of a cycle is a cycle

[@لُطف-ب9خ]

Hello, how many chromatic number of (c7) power 2 ????

[@jannreyjoshuagarcia1755]

at time 5:45 i think you can do it with 3 colors

[@steve4684]

Does someone know the outro song of this video? The musician is called vallow but i can not find the song...

[@WrathofMath]

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

[@davideperrone4702]

hi everybody, is there a video about interval graphs?

[@nadred5396]

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?

[@infomaniac8840]

Im pretty sure it's all on his iPad which he is screen recording.

[@ZeroTwo00002]

i think, now im ready to my D.math final exam, ty!

[@WrathofMath]

Good luck!

[@PunmasterSTP]

How'd the final go?

[@ZeroTwo00002]

@@PunmasterSTP i got 80 :DD

[@PunmasterSTP]

@@ZeroTwo00002 Way to go!

[@BEEd-3A-2023]

Thank you for making this

[@WrathofMath]

You're very welcome, thanks a lot for watching and let me know if you ever have any questions!

[@nainamat6861]

THANK YOU!!!😄😊

[@WrathofMath]

My pleasure! Thank you for watching! 😊

[@soveatinkuntur8167]

can you please make a video about list coloring

[@noorainkhan6699]

Tq for explaining it so well❣️❣️🙏

[@WrathofMath]

My pleasure, thanks for watching!

[@meganreader4363]

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

[@WrathofMath]

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: kzbin.info/www/bejne/l6TJmZd8f8Z6h7M

[@gift_tube8646]

Do lecture on how to calculate the chromatic number for a graph

[@camilomuianga7865]

It would be more interesting!

[@tiwaritejaswo]

Awesome. Thanks a ton.

[@WrathofMath]

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. kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@aishwaryar1998]

Could you please do a video on what is math and what are the things we can do with the help of math?

[@PunmasterSTP]

That's pretty general. Did you have anything more specific in mind?

[@ponnu1500]

Please upload a video about edge colouring

[@WrathofMath]

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!

[@ponnu1500]

@@WrathofMath thank you for your response

[@PunmasterSTP]

In the words of the great Calvin Harris, "Get some colours on!"

[@saiparn282]

Thank you so much!!!

[@WrathofMath]

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! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@BallerXhooperHighlights]

Thank you idol!

[@timmy2210]

Thank u!

[@WrathofMath]

Glad to help!

[@closingtheloop2593]

Thank god I found you

[@Local_Nerd]

Thanks

[@Andy-gp8qy]

👍👍👍👍

[@WrathofMath]

Thanks Andy! Many more videos on chromatic numbers and similar topics are coming, let me know if you ever have any requests!

[@closingtheloop2593]

i see orange red red

[@valquiriasantos8752]

Ik1w09

[@BelegaerTheGreat]

I'm not 5 years old