Colorful Mathematics: Part I
4. Vertex Colorings
This graph has a subgraph consisting of 5 vertices each joined to the other 4 vertices . A graph which has k vertices, each joined to all the others is known as a complete graph with k vertices, and is denoted Kk. When a graph has a subgraph which is a complete graph, this subgraph is known as a clique. The graph above has a clique with 4 vertices which is not a subgraph of a clique with 5 vertices, and a clique with 5 vertices. (Note that cliques on 5 vertices contain cliques on 4 vertices. Sometimes the definition of clique requires that it be "maximal" with respect to not being contained in a larger complete graph.) Since the vertices in a clique are all joined to each other, the vertex chromatic number of a graph must be at least as large as the size of the largest clique in the graph. It is traditional to use the notation χ(G) for the vertex chromatic number of a graph, the minimum number of colors that can be used to color the vertices of a graph so that vertices joined by an edge get different colors and to use ω(G) to denote the size of the largest clique subgraph in a graph. As just explained:
The graph in Figure 3 has a five-vertex clique, so its vertex-coloring number is at least 5. It is easy to check that the vertex chromatic number of this graph is 5 by actually coloring all the vertices of the graph with five colors.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance