We consider how to generate graphs of arbitrary size whose chromatic numbers can be chosen (or are well-bounded) for testing graph coloring algorithms on parallel computers. For the distance-1 graph coloring problem, we identify three classes of graphs with this property. The first is the Erdős-Rényi random graph with prescribed expected degree, where the chromatic number is known with high probability. It is also known that the Greedy algorithm colors this graph using at most twice the number of colors as the chromatic number. The second is a random geometric graph embedded in hyperbolic space where the size of the maximum clique provides a tight lower bound on the chromatic number. The third is a deterministic graph described by Mycielski, where the graph is recursively constructed such that its chromatic number is known and increases with graph size, although the size of the maximum clique remains two. For Jacobian estimation, we bound the distance-2 chromatic number of random bipartite graphs by considering its equivalence to distance-1 coloring of an intersection graph. We use a “balls and bins” probabilistic analysis to establish a lower bound and an upper bound on the distance-2 chromatic number. The regimes of graph sizes and probabilities that we consider are chosen to suit the Jacobian estimation problem, where the number of columns and rows are asymptotically nearly equal, and have number of nonzeros linearly related to the number of columns. Computationally we verify the theoretical predictions and show that the graphs are often be colored optimally by the serial and parallel Greedy algorithms.
more »
« less
Fractional DP‐colorings of sparse graphs
DP‐coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvořák and Postle [J. Combin. Theory Ser. B 129 (2018), pp. 38–54]. In this paper we introduce and study the fractional DP‐chromatic number . We characterize all connected graphs such that : they are precisely the graphs with no odd cycles and at most one even cycle. By a theorem of Alon, Tuza, and Voigt [Discrete Math. 165–166 (1997), pp. 31–38], the fractional list‐chromatic number of any graph equals its fractional chromatic number . This equality does not extend to fractional DP‐colorings. Moreover, we show that the difference can be arbitrarily large, and, furthermore, for every graph of maximum average degree . On the other hand, we show that this asymptotic lower bound is tight for a large class of graphs that includes all bipartite graphs as well as many graphs of high girth and high chromatic number.
more » « less- NSF-PAR ID:
- 10126561
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Journal of Graph Theory
- Volume:
- 93
- Issue:
- 2
- ISSN:
- 0364-9024
- Page Range / eLocation ID:
- p. 203-221
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The objective of this study is to develop a mathematical framework for determining the minimum number of parts required in a product to satisfy a list of functional requirements (FRs) given a set of connections between FRs. The problem is modeled as a graph coloring technique in which a graph G with n nodes (representing the FRs) and m edges (representing the connections between the FRs) is studied to determine the graph’s chromatic number c(G), which is the minimum number of colors required to properly color the graph. The chromatic number of the graph represents the minimum number of parts needed to satisfy the list of FRs. In addition, the study calculates the computational efficiency of the proposed algorithm. Several examples are provided to show the application of the proposed algorithm.more » « less
-
Abstract Recently, Dvořák, Norin, and Postle introduced flexibility as an extension of list coloring on graphs (J Graph Theory 92(3):191–206, 2019, https://doi.org/10.1002/jgt.22447 ). In this new setting, each vertex v in some subset of V ( G ) has a request for a certain color r ( v ) in its list of colors L ( v ). The goal is to find an L coloring satisfying many, but not necessarily all, of the requests. The main studied question is whether there exists a universal constant $$\varepsilon >0$$ ε > 0 such that any graph G in some graph class $$\mathscr {C}$$ C satisfies at least $$\varepsilon$$ ε proportion of the requests. More formally, for $$k > 0$$ k > 0 the goal is to prove that for any graph $$G \in \mathscr {C}$$ G ∈ C on vertex set V , with any list assignment L of size k for each vertex, and for every $$R \subseteq V$$ R ⊆ V and a request vector $$(r(v): v\in R, ~r(v) \in L(v))$$ ( r ( v ) : v ∈ R , r ( v ) ∈ L ( v ) ) , there exists an L -coloring of G satisfying at least $$\varepsilon |R|$$ ε | R | requests. If this is true, then $$\mathscr {C}$$ C is called $$\varepsilon$$ ε - flexible for lists of size k . Choi, Clemen, Ferrara, Horn, Ma, and Masařík (Discrete Appl Math 306:20–132, 2022, https://doi.org/10.1016/j.dam.2021.09.021 ) introduced the notion of weak flexibility , where $$R = V$$ R = V . We further develop this direction by introducing a tool to handle weak flexibility. We demonstrate this new tool by showing that for every positive integer b there exists $$\varepsilon (b)>0$$ ε ( b ) > 0 so that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_b$$ K 4 , C 5 , C 6 , C 7 , B b is weakly $$\varepsilon (b)$$ ε ( b ) -flexible for lists of size 4 (here $$K_n$$ K n , $$C_n$$ C n and $$B_n$$ B n are the complete graph, a cycle, and a book on n vertices, respectively). We also show that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_5$$ K 4 , C 5 , C 6 , C 7 , B 5 is $$\varepsilon$$ ε -flexible for lists of size 4. The results are tight as these graph classes are not even 3-colorable.more » « less
-
more » « less
A proper edge‐coloring of a given undirected graph with natural numbers identified with colors is an
interval (or consecutive) coloring if the colors of edges incident to each vertex form an interval of consecutive integers. Not all graphs admit such an edge‐coloring and the problem of deciding whether a graph is interval colorable is NP‐complete. For a graph that is not interval colorable, determining a graph invariant called the (minimum)deficiency is a widely used approach. Deficiency is a measure of how close the graph is to have an interval coloring. The majority of the studies in the literature either derive bounds on the deficiency of general graphs or calculate the deficiency of graphs belonging to some special graph classes. In this work, we derive integer programming formulations of theMinimum Deficiency Problem which seeks to find the exact deficiency value of a graph, given a bound on the number of colors that can be used. We further enhance the formulation by introducing a family of valid inequalities. Then, we solve our model via abranch‐and‐cut algorithm . Our computational study on a large set of random graphs illustrates the strength of our formulation and the efficiency of the proposed approach. -
null (Ed.)Graph parameters such as the clique number, the chromatic number, and the independence number are central in many areas, ranging from computer networks to linguistics to computational neuroscience to social networks. In particular, the chromatic number of a graph (i.e., the smallest number of colors needed to color all vertices such that no two adjacent vertices are of the same color) can be applied in solving practical tasks as diverse as pattern matching, scheduling jobs to machines, allocating registers in compiler optimization, and even solving Sudoku puzzles. Typically, however, the underlying graphs are subject to (often minor) changes. To make these applications of graph parameters robust, it is important to know which graphs are stable for them in the sense that adding or deleting single edges or vertices does not change them. We initiate the study of stability of graphs for such parameters in terms of their computational complexity. We show that, for various central graph parameters, the problem of determining whether or not a given graph is stable is complete for $\Phi_2^p$, a well-known complexity class in the second level of the polynomial hierarchy, which is also known as “parallel access to NP.”more » « less
