More Like this

1. Graph coloring and semidefinite rank

   https://doi.org/10.1007/s10107-024-02085-0  

   Mirka, Renee; Smedira, Devin; Williamson, David P (July 2024, Mathematical Programming)

   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
2. DP‐Coloring of Graphs From Random Covers

   https://doi.org/10.1002/rsa.70000  

   Bernshteyn, Anton; Dominik, Daniel; Kaul, Hemanshu; Mudrock, Jeffrey_A (February 2025, Random Structures & Algorithms)

   ABSTRACT DP‐coloring (also called correspondence coloring) of graphs is a generalization of list coloring that has been widely studied since its introduction by Dvořák and Postle in 2015. Intuitively, DP‐coloring generalizes list coloring by allowing the colors that are identified as the same to vary from edge to edge. Formally, DP‐coloring of a graph is equivalent to an independent transversal in an auxiliary structure called a DP‐cover of . In this paper, we introduce the notion of random DP‐covers and study the behavior of DP‐coloring from such random covers. We prove a series of results about the probability that a graph is or is not DP‐colorable from a random cover. These results support the following threshold behavior on random ‐fold DP‐covers as where is the maximum density of a graph: Graphs are non‐DP‐colorable with high‐probability when is sufficiently smaller than , and graphs are DP‐colorable with high‐probability when is sufficiently larger than . Our results depend on growing fast enough and imply a sharp threshold for dense enough graphs. For sparser graphs, we analyze DP‐colorability in terms of degeneracy. We also prove fractional DP‐coloring analogs to these results. 

   more » « less
3. Max cut and semidefinite rank

   https://doi.org/10.1016/j.orl.2024.107067  

   Mirka, Renee; Williamson, David P (March 2024, Operations Research Letters)

   This paper considers the relationship between semidefinite programs (SDPs), matrix rank, and maximum cuts of graphs. Utilizing complementary slackness conditions for SDPs, we investigate when the rank 1 feasible solution corresponding to a max cut is the unique optimal solution to the Goemans-Williamson max cut SDP by showing the existence of an optimal dual solution with rank n-1 . Our results consider connected bipartite graphs and graphs with multiple max cuts. We conclude with a conjecture for general graphs. 

   more » « less
4. Three coloring via triangle counting

   Hamaker, Zachary; Vatter, Vincent (August 2023, The Australasian journal of combinatorics)

   Albert, Michael; Billington, Elizabeth J (Ed.)

   In the first partial result toward Steinberg’s now-disproved three coloring conjecture, Abbott and Zhou used a counting argument to show that every planar graph without cycles of lengths 4 through 11 is 3-colorable. Implicit in their proof is a fact about plane graphs: in any plane graph of minimum degree 3, if no two triangles share an edge, then triangles make up strictly fewer than 2/3 of the faces. We show how this result, combined with Kostochka and Yancey’s resolution of Ore’s conjecture for k = 4, implies that every planar graph without cycles of lengths 4 through 8 is 3-colorable. 

   more » « less
5. Equitable List Coloring of Planar Graphs With Given Maximum Degree

   https://doi.org/10.1002/jgt.23203  

   Kierstead, H A; Kostochka, Alexandr; Xiang, Zimu (April 2025, Journal of Graph Theory)

   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