A Proper Coloring of a Graph Is an Assignment of Colors to the Vertices of the Graph So That No Two Adjacent Vertices Have the Same Color. Usually We Drop the Word Proper'' Unless Other Types of Coloring Are Also Under Discussion. of Course, the Colors'' Don't Have to Be Actual Colors They Can Be any Distinct Labels—Integers, For Example. If a Graph Is Not Connected, Each Connected Component Can Be Colored Independently Except Where Otherwise Noted, We Assume Graphs Are Connected.
If the Vertices of a Graph Represent Academic Classes, and Two Vertices Are Adjacent If the Corresponding Classes Have People In Common, Then a Coloring of the Vertices Can Be Used to Schedule Class Meetings. Here the Colors Would Be Schedule Times, Such As 8Mwf, 9Mwf, 11Tth, Etc.