Given an undirected graph G = (V, E), a coloring of G is an assignment of colors to the vertices V such that for each edge (i, j) ∈ E, i and j receive different colors. The chromatic number of G, denoted χ(G), is the minimum number of colors used such that a coloring of G exists. The clique number of a graph G, denoted ω(G), is the size of the largest clique in the graph; a set S ⊆ V of vertices is a clique if for every distinct pair i, j ∈ S, (i, j) ∈ E. It is easy to see that ω(G) ≤ χ(G). Graph colorings have been intensively studied for over a century. One of the most well-known theorems of graph theory, the four-color theorem, states that four colors suffice to color any planar graph G; the problem of four-coloring a planar graph can be traced back to the 1850 s, and the computer-assisted proof of the four-color theorem by Appel and Haken [2,3] is considered a landmark in graph theory. See Jensen and Toft [9] and Molloy and Reed [13] for book-length treatments of graph coloring in general. Fritsch and Fritsch [7], Ore [14], and Wilson [17] provide book-length treatments of the four-color theorem in particular, and Robertson, Sanders, Seymour, and Thomas [15] give a simplified computer-assisted proof of the four-color theorem.
This paper considers the use of semidefinite programming in graph coloring. The connection between semidefinite programming and graph coloring was initiated by Lovász [12], who introduced the Lovász theta function, θ( Ḡ), which is computable via semidefinite programming; Ḡ is the complement of graph G, in which all edges of G are replaced by nonedges and vice versa. Lovász showed that ω(G) ≤ θ( Ḡ) ≤ χ(G); Knuth [11] gives a helpful overview of this result.
Another use of semidefinite programming for graph coloring was introduced by Karger, Motwani, and Sudan [10] (KMS), who showed how to color k-colorable graphs with O(n 1-3/(k+1) log 1/2 n) colors in polynomial time using semidefinite programming, where n is the number of vertices in the graph. A starting point of the algorithm of KMS is the following vector program, which KMS called the strict vector chromatic number; the vector program can be solved via semidefinite programming: minimize α subject to v i • v j = α, ∀(i, j) ∈ E,
KMS observe that any k-colorable graph has a feasible solution to the vector program with α = -1/(k -1): let v 1 = (1, 0, . . . , 0) ∈ k-1 and inductively find v i ∈ k-1 for 1 < i ≤ k -1 by setting v i (j) = 0 for j > i and otherwise solving the system of equations given by v l
j=1 v j , then assign one color to each of the vectors v i . This guarantees that each vector v i has unit length (so v i • v i = 1) and that for any edge (i, j) ∈ E, v i •v j = -1/(k -1). It is important for the following discussion to observe that this solution lies in a (k -1)-dimensional space. KMS also observe that there is a natural connection between the strict vector chromatic number and the Lovász theta function. In particular, for the solution α to the vector program above, it is possible to show that α = 1/(1θ( Ḡ)) (see [10,Theorem 8.2]). If the graph G has a k-clique K k and is k-colorable, then by Lovász's theorem, θ( Ḡ) = k, and so the feasible solution with α = -1/(k -1) is an optimal solution. It is also possible to argue directly that a graph with a K k must have α ≥ -1/(k -1), again proving that the feasible solution given above is an optimal one. We will call the feasible solution above (in which the vectors are recursively constructed) the reference solution.
The goal of this paper is to explore situations in which the reference solution is the unique optimal solution of a semidefinite program (SDP), either the SDP corresponding to the strict vector chromatic number given above, or another that we will give shortly. To do this, we will use complementary slackness conditions for semidefinite programs. Consider the primal and dual SDPs shown in standard form below, where the constraint that X is a positive semidefinite matrix is represented by X 0, and we take the outer product of matrices, so that C • X, for instance, denotes
Duality theory for semidefinite programs (e.g. Alizadeh [1]) shows that for any feasible primal solution X and any feasible dual solution y, C • X ≥ b T y. Furthermore if C • X = b T y, so that the solutions are optimal, then it must be the case that rank(X) + rank(S) ≤ , and XS = 0, where we refer to rank(X) and rank(S) as the primal rank and dual rank, respectively. Thus if we want to show that any optimal primal solution has rank at most r, it suffices to show the existence of an optimal dual solution of rank at leastr. Turning back to the strict vector chromatic number vector program, the corresponding dual vector program is maximize
Thus, given a k-colorable graph G with a K k , if we can show a dual feasible solution of value -1/(k -1) and rank nk + 1, then we know that the primal solution must have rank at most k -1; in the cases we can show this, we can also show that the reference solution is the unique primal optimal solution. We will for shorthand say that there is an optimal dual solution of sufficiently high rank.
Our first result is to partially characterize the set of graphs for which the optimal solution to the strict vector chromatic number vector program is the reference solution. In particular, we can show that if the graph is a (k -1)-tree, then the reference solution is the unique optimal solution to the SDP. In the opposite direction, if the graph is not uniquely colorable, then the dual does not have sufficiently high rank, and there exist optimal primal solutions that are not the reference solution and are at least k-dimensional. A (k -1)-tree is a graph constructed by starting with a complete graph on k vertices. We then iteratively add vertices v; for each new vertex v, we add k -1 edges from v to previously added vertices such that v together with these k -1 neighbors form a clique. A k-colorable graph is uniquely colorable if it has only one possible coloring up to a permutation of the colors. The k-tree graphs are easily shown to be uniquely colorable. In the case of planar graphs with a K 4 , these results imply a complete characterization of the graphs for which the optimal solution is the reference solution, since it is known that the uniquely 4-colorable planar graphs are exactly the planar 3-trees, also known as the Apollonian networks [6]. We argue that it is not surprising that graphs are not uniquely k-colorable do not have the reference solution as the sole optimal solution; we show that one can find a convex combination of the two different reference solutions corresponding to the two different colorings that gives an optimal SDP solution of rank higher than k -1, and clearly the convex combination is also feasible for the SDP.
To get around the issue of unique colorability, we instead look for minimumcost feasible solutions to the SDP above. That is, given a cost matrix C, we look to find optimal solutions to the primal SDP
where E ii is the matrix with a 1 at position ii and 0 elsewhere and for e = (i, j), E e is the matrix with 1 at positions ij and ji and 0 elsewhere. Once again, the reference solution is a feasible solution to the primal SDP. The goal now is to find a cost function C such that there is an optimal dual solution of sufficiently high rank (here rank nk + 1), so that the reference solution is the unique optimal solution to the primal SDP. We show that it is always possible to find a cost function C such that the dual has sufficiently high rank. Our construction of C depends on the coloring of the graph; however, we do show that such a C exists. Furthermore, the construction of C suggests a heuristic for finding a coloring of the graph, and we show that the heuristic works well. We enumerated all maximal planar graphs of up to 14 vertices containing a K 4 . The heuristics successfully colored all graphs of up to 11 vertices, and at least 99.75% of all graphs on 12, 13, and 14 vertices. The heuristics involve repeatedly solving semidefinite programs, and thus are not practical for large graphs (although they still run in polynomial time). However, we view them as a proof of concept that it might be possible to use our framework to reliably 4-color planar graphs.
Our interest in this direction of research was prompted by the Colin de Verdière invariant [5] (see also [16] for a useful survey of the invariant). A generalized Laplacian L = ( ij ) of graph G is a matrix such that the entries ij < 0 when (i, j) ∈ E, and ij = 0 when (i, j) / ∈ E. The Colin de Verdiére invariant, μ(G), is defined as follows.
1. L has exactly one negative eigenvalue of multiplicity one; 2. there is no nonzero matrix X = (x ij ) such that LX = 0 and such that x ij = 0 whenever i = j or ij = 0.
Colin de Verdiére shows that μ(G) ≤ 3 if and only if G is planar; in other words, if G is planar any generalized Laplacian of G with exactly one negative eigenvalue of multiplicity 1 will have rank at least n -3 (modulo the second condition on the invariant, which we will ignore for the moment). Other results show that G is outerplanar if and only if μ(G) ≤ 2, and G is a collection of paths if and only if μ(G) ≤ 1. Colin de Verdière [5] conjectures that χ(G) ≤ μ(G) + 1; this result is known to hold for μ(G) ≤ 4. We note that the part of the dual matrix -
indeed a generalized Laplacian L of a planar graph when the z e ≥ 0 for all e ∈ E, and that if G is connected, then the y i can be adjusted so that this matrix has a single negative eigenvalue of multiplicity one. Thus this part of the matrix, under these conditions, must have sufficiently high rank, as desired to verify that the optimal primal solution is the reference solution. This would show that if the graph G has a clique on μ(G) + 1 vertices, then indeed χ(G) = μ(G) + 1. So, for example, this would prove that any planar graph with a K 4 can be four-colored, leading to a non-computer assisted proof of the four-color theorem. However, we do not know how to find the corresponding cost matrix C or show that the dual S we find is optimal. Still, we view our heuristics as a step towards finding a way to construct the cost matrix C without knowledge of the coloring, and without using the proofs of the four-color theorem that have been developed thus far.
The rest of this paper is structured as follows. In Sect. 2, we give some preliminary results on semidefinite programming. In Sect. 3, we show our results for the strict vector chromatic number SDP, and show that (k -1)-trees imply dual solutions of sufficiently high rank, while graphs that are not uniquely colorable imply that such dual solutions cannot exist. In Sect. 4, we turn to the SDP with cost matrix C, and show that for any k-colorable graph with a k-clique, a cost matrix C exists that gives rise to a dual of sufficiently high rank. In Sect. 5, we give two heuristics for coloring planar graphs based on our construction of the cost matrix C, and show a case where the heuristic fails to find a 4-coloring of a planar graph. We give some open questions in Sect. 6. For space reasons, many proofs are omitted.
In this section, we recall some basic facts about semidefinite matrices and semidefinite programs that we will use in subsequent sections.
Recall the primal and dual semidefinite programs (P ) and (D) from the introduction. We always have weak duality for semidefinite programs, so that the following holds. Fact 1. Given any feasible X for (P ) and y for (D), C • X ≥ b T y.
Thus if we can produce a feasible X for (P ) and a feasible y for (D) such that C • X = b T y, then X must be optimal for (P ) and y optimal for (D).
The following is also known, and is the semidefinite programming version of complementary slackness conditions for linear programming.
Fact 2. [1, Theorem 2.10, Corollary 2.11] For optimal X for (P ) and y for (D), XS = 0 and rank(X) + rank(S) ≤ .
Semidefinite programs and vector programs (such as the strict vector chromatic vector program) are equivalent because a symmetric X ∈ n×n is positive semidefinite if and only if X = QDQ T for a real matrix Q ∈ n×n and diagonal matrix D in which the entries of D are the eigenvalues of X, and the eigenvalues are all nonnegative. We can then consider D 1/2 , the diagonal matrix in which each diagonal entry is the square root of the corresponding entry of D.
and similarly, given the vectors v i , we can construct a semidefinite matrix X with x ij = v i • v j . We also make the following observation based on this decomposition.
Observation 1. Given a semidefinite matrix X = QDQ T ∈ n×n , rank(X) = d if and only if the vectors v i ∈ n with v i the ith row of QD 1/2 are supported on just d coordinates.
Recall the strict vector chromatic SDP given in the introduction, labeled (SVCN-P). In what follows we will let the matrix X = (X ij ) be the SDP matrix such that X ij = v i • v j and S = (S ij ) be the SDP matrix related to the dual solution (SVCN-D) such that S ij = u i • u j . Lemma 1. Given an optimal primal solution X to (SVCN-P) and optimal dual solution S to (SVCN-D), we have that rank(X) + rank(S) ≤ n.
Our main result for this section is about graphs that are (k -1)-trees. Definition 2. A (k -1)-tree with n vertices is an undirected graph constructed by beginning with the complete graph on k vertices and repeatedly adding vertices in such a way that each new vertex, v, has k -1 neighbors that, together with v, form a k-clique.
An easy inductive argument shows that these graphs are k-colorable. Also, (k -1)-trees are known to be uniquely k-colorable, where uniquely colorable means every coloring produces that same vertex partitioning. Once k colors are assigned to the initial complete graph with k vertices, the color of each new vertex is uniquely determined by its k -1 neighbors. This partitioning into color classes is unique up to permuting the colors. Note that by construction, a (k -1)-tree contains a K k . By discussion in the introduction, the optimal value of (SVCN-P) for a (k -1)-tree will be exactly -1/(k -1).
Our goal is to show there is a feasible solution to the dual (SVCN-D) with high rank. In particular, given a (k-1)-tree with n vertices, we show the existence of a dual solution with rank at least nk + 1. This ensures that any primal solution has rank at most k -1; we show that the reference solution is the unique optimal primal solution. This is formalized in the following theorem.
Theorem 1. Given a (k -1)-tree G with n vertices, there is an optimal dual solution S to (SVCN-D) with rank at least n-k +1, and thus any optimal primal solution X to (SVCN-P) has rank at most k -1.
We subsequently prove that the reference solution is indeed the unique optimal solution in this case.
To prove Theorem 1, we need a number of supporting lemmas. We begin with the following. Lemma 2. Let tri(G) denote the number of triangles in a (k -1)-tree, G. Then, for a (k -1)-tree G with n vertices,
Consider a (k -1)-tree G with n vertices. For v ∈ V we denote the neighborhood of v by N (v) = {u : (u, v) ∈ E}. We define the following matrix S(G) which may be referred to as
We will show that S(G) is an optimal dual solution with rank nk + 1. First, we show S(G) is a feasible solution with help from the following lemma.
Lemma 3. For a (k -1)-tree G with n vertices, S(G) is positive semidefinite.
Proof. Observe that it suffices to show S (G) = k(k -1)(nk + 1)S(G) is positive semidefinite (PSD) since k(k-1)(n-k+1) > 0 for n ≥ k. We proceed by induction. First consider (k -1)-trees with k vertices. There is only one, G = K k . Furthermore, S (K k ) is equal to the all-ones matrix which has eigenvalues k and 0 with multiplicity k -1 and thus is PSD. Now assume there is some integer n such that for every (k -1)-tree, G, with at most n vertices, S (G) is PSD. Consider a (k -1)-tree G with n + 1 vertices. Since it is a (k -1)-tree, it can be constructed from some smaller (k -1)-tree G with n vertices by adding a vertex v and (k -1) edges that form a k clique with the k -1 neighbors. By assumption, S (G ) is PSD. Let I be the set of indices of the k -1 neighbors of v. Then we observe that S (G) = T + v n+1 v T n+1 where 2 ≥ 0 where the first inequality is due to T being PSD since S (G ) is PSD.
Proof. Lemma 3 shows that S(G) is PSD. To complete this claim, we must show that the dual constraints are satisfied. That S(G) ij = 0 for (i, j) / ∈ E is clear by construction. The other constraint requires i =j s ij ≥ 1. Using (1) and ( 2) from Lemma 2 we can prove that the inequality holds; the algebra is omitted for space reasons.
We can now show that S(G) is an optimal dual solution.
Theorem 3. For a (k -1)-tree G with n vertices, S(G) is an optimal dual solution.
Proof. We remarked earlier that the optimal primal value for a (k -1)-tree is -1/(k -1). Thus for S(G) to be an optimal dual solution, it suffices to show thati S ii = -1/(k -1). Again using (1) from Lemma 2, we have
Finally, we want to show that for a (k -1)-tree G with n vertices, S(G) has rank at least nk + 1. This guarantees that any primal solution has rank at most k -1.
Theorem 4. For a (k-1)-tree G with n vertices, S(G) has rank at least n-k+1.
to the all-ones matrix. Assuming the claim is true for all (k -1)-trees with at most n vertices, we consider a (k -1)-tree G with n + 1 vertices. We again use the decomposition
where
and G is a (k -1)-tree with n vertices acquired by removing vertex n + 1 with exactly k -1 neighbors, i ∈ I, from G. Note dim(ker(T )) = dim(ker(S (G )) + 1 ≤ k by assumption. Now assume x ∈ ker(S (G)). Then
Since T and v n+1 v T n+1 are both PSD, this implies x T T x = 0 and
This implies dim(ker(S (G)) < dim(ker(T )) ≤ k, so rank(S (G)) ≥ (n + 1)k + 1.
Theorem 1. Given a (k -1)-tree G with n vertices, there is an optimal dual solution S to (SVCN-D) with rank at least n-k +1, and thus any optimal primal solution Xto (SVCN-P) has rank at most k -1.
Proof. Theorem 1 follows as an immediate consequence of Lemma 4, Theorem 3, and Theorem 4.
We now turn to showing that the reference solution is indeed the optimal solution in the case of (k -1)-trees.
Theorem 2. The reference solution is the unique optimal primal solution (up to rotation) for a (k -1)-tree G = (V, E).
Theorem 2 shows that we can partition the vertices of a (k -1)-tree into k sets with each set associated to a different vector assigned in the low rank primal solution. Since vertices u, v are only in the same set in the partition if they were assigned the same vector in the primal solution, it is not possible for neighbors to be in the same set. We can then produce a valid coloring of the vertices by associating one color to each set in the partition.
We now turn to characterizing cases in which we cannot find dual solutions of sufficiently high rank by looking at potential solutions of vector colorings for graphs without unique colorings. In particular, we restrict our attention to graphs that have multiple distinct k-colorings and contain a k-clique. These assumptions provide information about the optimal objective function values.
There exists a primal solution to the strict vector chromatic number program for G with rank greater than k -1, and thus by Fact 2 the rank of any optimal dual solution must be less than nk + 1.
While we have shown that (k-1)-trees have sufficiently high dual rank for the standard vector chromatic number SDP, it would be nice if we could completely characterize which graphs have high dual rank. A reasonable guess would be that a k-colorable graph G containing a k-clique has high dual rank if and only if it is uniquely colorable. This assertion is true for the important special case of planar graphs.
Proof. Fowler [6] shows that uniquely-colorable planar graphs are exactly the set of planar 3-trees. By Theorem 1 we know such graphs have dual rank at least n -3. Furthermore, Theorem 5 shows that graphs with multiple colorings have primal solutions with rank more than 3 and therefore do not have dual solutions with rank n -3. Unfortunately, the following example shows unique colorability is not sufficient in general for a sufficiently high dual rank. Modifying a uniquely 3-colorable example of Hillar and Windfeldt [8] and computing the primal and dual SDPs of this graph returns solutions with objective value -0.5, primal rank of 24, and dual rank of 1. If the claim were true, we would expect all dual solutions to have rank at least 23.
Thus it remains an interesting open question to characterize in general cases in which graphs have sufficiently high dual rank and have the reference solution as the optimal primal solution.
Unfortunately, Theorem 5 seems to indicate that this method of looking for graphs that have high dual rank with the standard vector chromatic number SDP cannot be generalized to graphs with multiple colorings. To extend this method, we consider a modified SDP described next. The new program utilizes a new objective function. Here, we introduce the notion of a cost matrix C(G). The goal is to identify a C(G) such that minimizing C(G) • X forces X to have our desired rank. In particular, we consider the SDP given by (CP) in the introduction, along with its dual (CD).
To demonstrate how this cost matrix influences the behavior of rank(X), assume that G = (V, E) is a k-colorable graph containing a k-clique, but is not a (k -1)-tree. We still know there is a solution to the strict vector chromatic number program with α = -1/(k -1), and thus it is possible to find an X feasible for (CP). Now fix c : V → [k] to be a valid k-coloring of G. With this coloring, we can define an associated matrix C(G) in the following way:
Intuitively, the reference solution corresponding to the coloring given by c is the solution that will minimize total cost since we'll look for a solution X with X ij = 1 exactly when C(G) ij = -1; for such entries, we'll have the same vectors corresponding to vertices i and j. But we can show additionally that there is a dual optimal solution for cost function C(G) that has sufficiently high rank.
Theorem 6. For G and C(G) as described, there is an optimal dual solution with rank at least nk + 1, so that any optimal primal solution has rank at most k -1.
Let K be a k-clique in our k-colorable graph G. Let s i denote the sum of entries in column i of C(G). Consider the assignment of dual variables given by y i = s i for i / ∈ K, y i = s i -1 for i ∈ K, z e = -1 for e = (i, j), i, j ∈ K, i = j, and z e = 0 otherwise. We denote this assignment by (y, z). Lemma 5. The dual matrix S constructed with (y, z) is positive semidefinite. Theorem 7. The assignment (y, z) is an optimal dual solution, and the reference solution is an optimal primal solution.
Theorem 8. For G and C(G) as described, the reference solution is the unique optimal primal solution.
Two heuristics have been implemented and experimentally demonstrated success returning low-rank primal solutions for planar graphs. Neither algorithm assumes knowledge of a graph coloring. We tested these heuristics on all maximal planar graphs of up to 14 vertices that contain a K 4 . These graphs were generated via the planar graph generator plantri due to Brinkmann and McKay [4] found at https://users.cecs.anu.edu.au/ ∼ bdm/plantri/. The '-a' switch was used to produce graphs written in ascii format. The code was implemented in Python using the MOSEK Optimizer as the SDP solver. Both the graph data files and algorithm implementation can be found at https://github.com/rmirka/ four-coloring.git. Our results are shown in Table 1. The heuristics successfully colored all graphs with up to 11 vertices, and successfully colored 99.75% of the graphs of 12-14 vertices. We do not record the running time of the heuristics; because the heuristics involve repeatedly solving semidefinite programs, they are not competitive with other greedy or local search style heuristics. Our primary reason for studying these heuristics was to find whether we could reliably find a cost matrix C giving rise to a four-coloring for planar graphs.
For space reasons, we only describe the first heuristic. It is based on the coloring-dependent cost matrix discussed in Sect. 4. The algorithm first identifies a K 4 = {k 1 , k 2 , k 3 , k 4 } and finds an initial solution with C = 0. If the primal solution does not have low enough rank, the returned solution is used to update the cost matrix. Let S i = {v ∈ V : X vki = 1} for i = 1, 2, 3, 4. Let v be a vertex in V \ (∪ 4 i=1 S i ). Then there must exist i * ∈ {1, 2, 3, 4} such that X vk i * = 1 and X vk i * = -1/3; we update this S i * by adding v to it. Now, C is constructed based on the S j , j = 1, 2, 3, 4. In particular, for i = 1, 2, 3, 4, if n i denotes the number of vertices in S i , then for j = 1, . . . , n i -1, we set C rs = C sr = -1 where r and s are the jth and j + 1st vertices in S i . This new cost matrix C is used to compute an updated solution X. If X is of the desired rank, the algorithm terminates. If not, we first check to see if Xvk i * = 1, i.e. if our selected vertex from the previous iteration was successfully colored. If yes, we repeat the process beginning with our solution X and selecting a currently uncolored vertex. If v was not successfully colored, we remove the entry in the cost matrix corresponding to this assignment from the previous iteration and resolve the SDP while adding k i * to a list of 'bad' colors for v. We now repeat the process by selecting a new feasible color class for v (following the same rules as previously in addition to requiring it not be in the list of 'bad' colors for v) and constructing S i , i = 1, 2, 3, 4 and C accordingly.
In both heuristics, the termination condition is that the primal rank is equal to 3, but this doesn't necessarily guarantee that the dual rank is n -3. If instead one wanted to guarantee high dual rank, one could run the algorithm one more time, i.e. once the low-rank primal solution is achieved, extract the coloring and construct the corresponding C matrix as previously described in Theorem 6.
The example in Fig. 1 causes both heuristics to fail without coloring the graph. First we note the K 4 = {2, 5, 6, 7}. In the first iteration of the heuristic, these are the only four vertices that are assigned colors. In the second iteration, both heuristics successfully color vertex 1 to match vertex 6. However, afterwards each heuristic is unable to color any more vertices (it tries and fails on all other possible colors for the remaining vertices).
We close with several open questions. We were unable to give a complete characterization of the k-colorable graphs with a K k for which the strict vector chromatic number (SVCN-P) has a unique primal solution of the reference solution. Such graphs must be uniquely colorable, but clearly some further restriction is needed.
When we know the coloring, we can produce a cost matrix C for the semidefinite program (CP) such that the reference solution is the unique optimal solution and it must have rank k-1. We wondered whether one could use (CP) in a greedy coloring scheme, by incrementally constructing the matrix C; the graph in Fig. 1 shows that our desired scheme does not work in a straightforward manner. Possibly one could consider an algorithm with a limited amount of backtracking, as long as one could show that the algorithm continued to make progress against some metric. Another open question is whether one can somehow directly produce a cost matrix C leading to a dual solution of sufficiently high rank that does not need knowledge of the coloring. And we conclude with the open question that first motivated this work: is it possible to use the Colin de Verdière parameter to produce this matrix C?