Graph ColoringsWe are no going to consider different ways of coloring graphs. More precisely, we shall color the vertices of a graph, observing two rules: every vertex must be colored, and two vertices linked by an edge cannot be given the same color. If n is a natural number, then a graph is said to be ncolorable if it can be colored using n different colors, but not with few colors than n. Which graphs can be colored in one color? It is easy to see that each vertex of the graph must be isolated. Here is the only onecolorable graph with 13 vertices: Which graphs are 2colorable? One can prove that these are exactly the bipartite graphs. Here is a complete bipartite graph with 5 vertices on one side and 4 on the other; it has been colored using just 2 colors.
