Vertex Colorings and the Chromatic Number of Graphs | Graph Theory

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: ◆ Donate on PayPal: ◆ Support Wrath of Math on Patreon: 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 Spotify: Vallow SoundCloud: ******************************************************************** WRATH OF MATH Follow Wrath of Math on... ● Instagram: ● Facebook: ● Twitter: My Music Channel: