An official website of the United States government
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
Quasi-Stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality
We propose quasi-stable coloring , an approximate version of stable coloring. Stable coloring, also called color refinement, is a well-studied technique in graph theory for classifying vertices, which can be used to build compact, lossless representations of graphs. However, its usefulness is limited due to its reliance on strict symmetries. Real data compresses very poorly using color refinement. We propose the first, to our knowledge, approximate color refinement scheme, which we call quasi-stable coloring. By using approximation, we alleviate the need for strict symmetry, and allow for a tradeoff between the degree of compression and the accuracy of the representation. We study three applications: Linear Programming, Max-Flow, and Betweenness Centrality, and provide theoretical evidence in each case that a quasi-stable coloring can lead to good approximations on the reduced graph. Next, we consider how to compute a maximal quasi-stable coloring: we prove that, in general, this problem is NP-hard, and propose a simple, yet effective algorithm based on heuristics. Finally, we evaluate experimentally the quasi-stable coloring technique on several real graphs and applications, comparing with prior approximation techniques.
more »
« less
- PAR ID:
- 10428132
- Date Published:
- Journal Name:
- Proceedings of the VLDB Endowment
- Volume:
- 16
- Issue:
- 4
- ISSN:
- 2150-8097
- Page Range / eLocation ID:
- 803 to 815
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In numerous graph signal processing applications, data is often missing for a variety of reasons, and predicting the missing data is essential. In this paper, we consider data on graphs modeled as bandlimited graph signals. Predicting or reconstructing the unknown signal values for such a model requires an estimate of the signal bandwidth. In this paper, we address the problem of estimating the reconstruction errors, minimizing which would thereby provide an estimate of the signal bandwidth. In doing so, we design a cross-validation approach needed for stable graph signal reconstruction and propose a method for estimating the reconstruction errors for different choices of signal bandwidth. Using this technique, we are able to estimate the reconstruction error on a variety of real-world graphs.more » « less
-
Graph coloring assigns a color to each vertex of a graph such that no two adjacent vertices get the same color. It is a key building block in many applications. In practice, solutions that require fewer distinct colors and that can be computed faster are typically preferred. Various coloring heuristics exist that provide different quality versus speed tradeoffs. The highest-quality heuristics tend to be slow. To improve performance, several parallel implementations have been proposed. This paper describes two improvements of the widely used LDF heuristic. First, we present a “shortcutting” approach to increase the parallelism by non-speculatively breaking data dependencies. Second, we present “color reduction” techniques to boost the solution of LDF. On 18 graphs from various domains, the shortcutting approach yields 2.5 times more parallelism in the mean, and the color-reduction techniques improve the result quality by up to 20%. Our deterministic CUDA implementation running on a Titan V is 2.9 times faster in the mean and uses as few or fewer colors as the best GPU codes from the literature.more » « less
-
null (Ed.)The claw is the graph $$K_{1,3}$$, and the fork is the graph obtained from the claw $$K_{1,3}$$ by subdividing one of its edges once. In this paper, we prove a structure theorem for the class of (claw, $$C_4$$)-free graphs that are not quasi-line graphs, and a structure theorem for the class of (fork, $$C_4$$)-free graphs that uses the class of (claw, $$C_4$$)-free graphs as a basic class. Finally, we show that every (fork, $$C_4$$)-free graph $$G$$ satisfies $$\chi(G)\leqslant \lceil\frac{3\omega(G)}{2}\rceil$$ via these structure theorems with some additional work on coloring basic classes.more » « less
-
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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.14778/3574245.3574264
