Reference no: EM131576280

Question: What can be said about the chromatic number of a graph that has Kn as a subgraph?

This algorithm can be used to color a simple graph: First, list the vertices v1, v2, v3,..., vn in order of decreasing degree so that deg(v1) ≥ deg(v2) ≥···≥ deg(vn). Assign color 1 to v1 and to the next vertex in the list not adjacent to v1 (if one exists), and successively to each vertex in the list not adjacent to a vertex already assigned color 1. Then assign color 2 to the first vertex in the list not already colored. Successively assign color 2 to vertices in the list that have not already been colored and are not adjacent to vertices assigned color 2. If uncolored vertices remain, assign color 3 to the first vertex in the list not yet colored, and use color 3 to successively color those vertices not already colored and not adjacent to vertices assigned color 3. Continue this process until all vertices are colored.