An undirected graph is -coloring if all vertices could be colored with at most different colors, such that all adjacent vertices have different colors. For example, a -clique is -coloring, and a tree is 2-coloring. The densest subgraph of a graph , is an induced subgraph of a vertex subset of with vertices and edges, such that its density (i.e., ) is highest among all induced subgraphs. In this article, we aim to prove that for a graph whose densest subgraph has a density , it is -coloring.
Proof
Let and . We prove it by induction. When , and the graph is 1-coloring.
Assume we have proved the case for . For any graph such that , we denote as the vertex set of its densest subgraph and assume its density is . Then we remove the smallest degree vertex of and derives a graph with vertices, which is proved to be -coloring and is the largest density of the new graph. Obviously, the degree of is no larger than . Otherwise, the total degree of all vertices in is larger than , which yields a density larger than . Therefore, can be colored with at most colors (if only considering its neighbours).
We claim that . Then is -coloring (note that if a graph is -coloring and , then it is also -coloring).
We prove it by contradiction. If , removing results in some induced subgraph with a larger density. However, by definition, the densest subgraph of is already the induced subgraph with the highest density. Therefore, it is impossible to find a denser subgraph by removing a vertex in .
By induction, the proof is done.
Finding a coloring scheme
We recursively remove the smallest degree vertex in . Specifically, we maintain a min-heap storing the degrees of all vertices. Initially, we insert all vertices into the heap. For each round, we extract the minimum degree vertex from the heap and remove the vertex. During the remove process, we need to update the degree of its neighbors (for a simple graph, the new degree of its neighbors should be ) and adjust the heap. With a binary heap, since extracting each vertex and updating the degree of each vertex is , and there are updates in total, the time complexity would be . With a Fibonacci heap, where decrease-key function could be done in , the time complexity would reduce to .
We record the sequence of removing vertices, i.e., the algorithm removes sequentially. To construct the coloring scheme, we reversely consider each vertex: let be an empty graph. We firstly add to and color it with . Then we add to and its corresponding edges in connecting (if exist). If are connected, we color with . Otherwise, it is colored with . Similarly, we add to and its edges to if exist, and color with the minimum possible color. Repeat this process until is inserted into and colored. The time complexity of this process is bounded by .
Therefore, the total time complexity of the algorithm is bounded by , and it is straightforward to prove its correctness using the similar technique in the induction proof.