An official website of the United States government
This paper considers the interplay between semidefinite programming, matrix rank, and graph coloring. Karger, Motwani, and Sudan give a vector program in which a coloring of a graph can be encoded as a semidefinite matrix of low rank. By complementary slackness conditions of semidefinite programming, if an optimal dual solution has high rank, any optimal primal solution must have low rank. We attempt to characterize graphs for which we can show that the corresponding dual optimal solution must have rank high enough that the primal solution encodes a coloring. In the case of the original Karger, Motwani, and Sudan vector program, we show that any graph which is a $$k$$-tree has sufficiently high dual rank, and we can extract the coloring from the corresponding low-rank primal solution. We can also show that if a graph is not uniquely colorable, then no sufficiently high rank dual optimal solution can exist. This allows us to completely characterize the planar graphs for which dual optimal solutions have sufficiently high dual rank, since it is known that the uniquely colorable planar graphs are precisely the planar 3-trees. We then modify the semidefinite program to have an objective function with costs, and explore when we can create an objective function such that the optimal dual solution has sufficiently high rank. We show that it is always possible to construct such an objective function given the graph coloring. The construction of the objective function gives rise to heuristics for 4-coloring planar graphs. We enumerated all maximal planar graphs with an induced $$K_4$$ of up to 14 vertices; the heuristics successfully found a 4-coloring for 99.75\% of them. Our research was motivated by trying to use semidefinite programming to prove the four-color theorem, which states that every planar graph can be colored with four colors. There is an intriguing connection of the Karger-Motwani-Sudan semidefinite program with the Colin de Verdi\`ere graph invariant (and a corresponding conjecture of Colin de Verdi\`ere), in which matrices that have some similarities to the dual feasible matrices of the semidefinite program must have high rank in the case that graphs are of a certain type; for instance, planar graphs have rank that would imply that the primal solution of the semidefinite program encodes a 4-coloring.
more »
« less
Coloring count cones of planar graphs
Abstract For a plane near‐triangulation with the outer face bounded by a cycle , let denote the function that to each 4‐coloring of assigns the number of ways extends to a 4‐coloring of . The Block‐count reducibility argument (which has been developed in connection with attempted proofs of the Four Color Theorem) is equivalent to the statement that the function belongs to a certain cone in the space of all functions from 4‐colorings of to real numbers. We investigate the properties of this cone for , formulate a conjecture strengthening the Four Color Theorem, and present evidence supporting this conjecture.
more »
« less
- PAR ID:
- 10363913
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Journal of Graph Theory
- Volume:
- 100
- Issue:
- 1
- ISSN:
- 0364-9024
- Page Range / eLocation ID:
- p. 84-100
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract It was conjectured by Hajós that graphs containing no ‐subdivision are 4‐colorable. Previous results show that any possible minimum counterexample to Hajós' conjecture, called Hajós graph, is 4‐connected but not 5‐connected. In this paper, we show that if a Hajós graph admits a 4‐cut or 5‐cut with a planar side then the planar side must be small or contains a special wheel. This is a step in our effort to reduce Hajós' conjecture to the Four Color Theorem.more » « less
-
A relative version of the Turaev–Viro invariants and the volume of hyperbolic polyhedral 3‐manifoldsAbstract We define a relative version of the Turaev–Viro invariants for an ideally triangulated compact 3‐manifold with nonempty boundary and a coloring on the edges, generalizing the Turaev–Viro invariants [36] of the manifold. We also propose the volume conjecture for these invariants whose asymptotic behavior is related to the volume of the manifold in the hyperbolic polyhedral metric [22, 23] with singular locus of the edges and cone angles determined by the coloring, and prove the conjecture in the case that the cone angles are sufficiently small. This suggests an approach of solving the volume conjecture for the Turaev–Viro invariants proposed by Chen–Yang [8] for hyperbolic 3‐manifolds with totally geodesic boundary.more » « less
-
ABSTRACT If is a list assignment of colors to each vertex of an ‐vertex graph , then anequitable‐coloringof is a proper coloring of vertices of from their lists such that no color is used more than times. A graph isequitably‐choosableif it has an equitable ‐coloring for every ‐list assignment . In 2003, Kostochka, Pelsmajer, and West (KPW) conjectured that an analog of the famous Hajnal–Szemerédi Theorem on equitable coloring holds for equitable list coloring, namely, that for each positive integer every graph with maximum degree at most is equitably ‐choosable. The main result of this paper is that for each and each planar graph , a stronger statement holds: if the maximum degree of is at most , then is equitably ‐choosable. In fact, we prove the result for a broader class of graphs—the class of the graphs in which each bipartite subgraph with has at most edges. Together with some known results, this implies that the KPW Conjecture holds for all graphs in , in particular, for all planar graphs. We also introduce the new stronger notion ofstrongly equitable(SE, for short) list coloring and prove all bounds for this parameter. An advantage of this is that if a graph is SE ‐choosable, then it is both equitably ‐choosable and equitably ‐colorable, while neither of being equitably ‐choosable and equitably ‐colorable implies the other.more » « less
-
ABSTRACT We prove that for any graph , the total chromatic number of is at most . This saves one color in comparison with the result of Hind from 1992. In particular, our result says that if , then has a total coloring using at most colors. When is regular and has a sufficient number of vertices, we can actually save an additional two colors. Specifically, we prove that for any , there exists such that: if is an ‐regular graph on vertices with , then . This confirms the Total Coloring Conjecture for such graphs .more » « less
