Numerical experiences with graph coloring algorithms

We consider the problem to color the vertices of a graph with a minimal number of colors. Sequential vertex (Sv) algorithms are mostly used for approximate solutions. For the selection of the colors all the approximation Sv-algorithms proposed in literature use the Min rule. In this paper a look-ahead rule is applied to determine a most ‘suitable’ color. Furthermore, the influence of the vertex order at the beginning of the Sv algorithm (Lf or Sl) in investigated. The tests are made on a sample of 3000 random graphs with up to 300 vertices.     

Variations on memetic algorithms for graph coloring problems

Graph vertex coloring with a given number of colors is a well-known and much-studied NP-complete problem. The most effective methods to solve this problem are proved to be hybrid algorithms such as memetic algorithms or quantum annealing. Those hybrid algorithms use a powerful local search inside a population-based algorithm. This paper presents a new memetic algorithm based on one of the most effective algorithms: the hybrid evolutionary algorithm (HEA) from Galinier and Hao (J Comb Optim 3(4): 379–397, 1999). The proposed algorithm, denoted HEAD—for HEA in Duet—works with a population of only two individuals. Moreover, a new way of managing diversity is brought by HEAD. These two main differences greatly improve the results, both in terms of solution quality and computational time. HEAD has produced several good results for the popular DIMACS benchmark graphs, such as 222-colorings for \({<}{} \texttt {dsjc1000.9}{>}\), 81-colorings for \({<}{} \texttt {flat1000\_76\_0}{>}\) and even 47-colorings for \({<}{} \texttt {dsjc500.5}{>}\) and 82-colorings for \({<}{} \texttt {dsjc1000.5}{>}\).     

Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces

A sequential graph coloring algorithm and a strict distributed (broadcasting type) algorithm , and an analysis of their performance in scales of random graph spaces is presented. For a space of graphs with n vertices and a mean degree d(n), the number of colors produced is almost surely bounded by about d(n)/logd(n), which is almost surely not more than twice the chromatic number, and the distributed algorithm terminates in O(Max(d(n),logn)) steps.     

Metaheuristics for robust graph coloring

This paper studies a robust graph coloring problem, which is a variant of the classical graph coloring problem, where penalties are charged for non-adjacent vertices that are assigned the same color. The problem can be formulated as an unconstrained quadratic programming problem, and has many applications in industry. Since the problem is known to be strongly NP-complete, we develop a number of metaheuristics for it, which are based on various encoding schemes, neighborhood structures, and search algorithms. Extensive experiments suggest that our metaheuristics with a partition based encoding scheme and an improvement graph based neighborhood outperform other methods tested in our study.     

Signed graph coloring

Coloring a signed graph by signed colors, one has a chromatic polynomial with the same enumerative and algebraic properties as for ordinary graphs. New phenomena are the interpretability only of odd arguments and the existence of a second chromatic polynomial counting zero-free colorings. The generalization to voltage graphs is outlined.     

A Branch-and-Cut algorithm for graph coloring

In this paper a Branch-and-Cut algorithm, based on a formulation previously introduced by us, is proposed for the Graph Coloring Problem. Since colors are indistinguishable in graph coloring, there may typically exist many different symmetrical colorings associated with a same number of colors. If solutions to an integer programming model of the problem exhibit that property, the Branch-and-Cut method tends to behave poorly even for small size graph coloring instances. Our model avoids, to certain extent, that bottleneck. Computational experience indicates that the results we obtain improve, in most cases, on those given by the well-known exact solution graph coloring algorithm Dsatur.     

Variable space search for graph coloring

Let G=(V,E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1,…,k}) to each vertex of G so that no edge has both endpoints with the same color. We propose a new local search methodology, called Variable Space Search, which we apply to the k-coloring problem. The main idea is to consider several search spaces, with various neighborhoods and objective functions, and to move from one to another when the search is blocked at a local optimum in a given search space. The k-coloring problem is thus solved by combining different formulations of the problem which are not equivalent, in the sense that some constraints are possibly relaxed in one search space and always satisfied in another. We show that the proposed algorithm improves on every local search used independently (i.e., with a unique search space), and is competitive with the currently best coloring methods, which are complex hybrid evolutionary algorithms.     

A memetic algorithm for graph coloring

Given an undirected graph G=(V,E)$G=(V\text{,}E)$ with a set V of vertices and a set E of edges, the graph coloring problem consists of partitioning all vertices into k independent sets and the number of used colors k is minimized. This paper presents a memetic algorithm (denoted by MACOL) for solving the problem of graph coloring. The proposed MACOL algorithm integrates several distinguished features such as an adaptive multi-parent crossover (AMPaX) operator and a distance-and-quality based replacement criterion for pool updating. The proposed algorithm is evaluated on the DIMACS challenge benchmarks and computational results show that the proposed MACOL algorithm achieves highly competitive results, compared with 11 state-of-the-art algorithms. The influence of some ingredients of MACOL on its performance is also analyzed.     

σ-polynomials and graph coloring

A new class of graph polynomials is defined. Tight bounds on the coefficients of the polynomials are given, and the exact polynomials for several classes of graphs are derived. The relationship of these polynomials to chromatic polynomials and graph coloring is discussed.     

Randomized online graph coloring

We study the problem of coloring graphs in an online manner. The only known deterministic online graph coloring algorithm with a sublinear performance function was found by [9.], 319–325). Their algorithm colors graphs of chromatic number χ with no more than (2χn)/log^* n colors, where n is the number of vertices. They point out that the performance can be improved slightly for graphs with bounded chromatic number. For three-chromatic graphs the number of colors used, for example, is O(n log log log n/log log n). We show that randomization helps in coloring graphs online. We present a simple randomized online algorithm to color graphs with expected number of colors O(2^χχ²n^{(χ−2)/(χ−1)}(log n)^1/(χ−1)). For three-colorable graphs the expected number of colors our algorithm uses is . All our algorithms run in polynomial time. It is interesting to note that our algorithm compares well with the best known polynomial time offline algorithms. For instance, the best polynomial time algorithm known for three-colorable graphs, due to [4.] pp. 554–562). We also prove a lower bound of Ω((1/(χ − 1))((log n/(12(χ + 1))) − 1)^χ−1) for the randomized model. No lower bound for the randomized model was previously known. For bounded χ, our result improves even the best known lower bound for the deterministic case: Ω((log n/log log n)^χ−1), due to Noga Alon (personal communication, September 1989).     

Asymmetric graph coloring games

We introduce the (a,b)‐coloring game, an asymmetric version of the coloring game played by two players Alice and Bob on a finite graph, which differs from the standard version in that, in each turn, Alice colors a vertices and Bob colors b vertices. We also introduce a related game, the (a,b)‐marking game. We analyze these games and determine the (a,b)‐chromatic numbers and (a,b)‐coloring numbers for the class of forests and all values of a and b. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 169–185, 2005     

Mixed graph edge coloring

We are interested in coloring the edges of a mixed graph, i.e., a graph containing unoriented and oriented edges. This problem is related to a communication problem in job-shop scheduling systems. In this paper we give general bounds on the number of required colors and analyze the complexity status of this problem. In particular, we provide NP-completeness results for the case of outerplanar graphs, as well as for 3-regular bipartite graphs (even when only 3 colors are allowed, or when 5 colors are allowed and the graph is fully oriented). Special cases admitting polynomial-time solutions are also discussed.     

A cutting plane algorithm for graph coloring

We present an approach based on integer programming formulations of the graph coloring problem. Our goal is to develop models that remove some symmetrical solutions obtained by color permutations. We study the problem from a polyhedral point of view and determine some families of facets of the 0/1-polytope associated with one of these integer programming formulations. The theoretical results described here are used to design an efficient Cutting Plane algorithm.     

A semidefinite programming-based heuristic for graph coloring

The Lovász θ-function is a well-known polynomial lower bound on the chromatic number. Any near-optimal solution of its semidefinite programming formulation carries valuable information on how to color the graph. A self-contained presentation of the role of this formulation in obtaining heuristics for the graph coloring problem is presented. These heuristics could be useful for coloring medium sized graphs as numerical results on DIMACS benchmark graphs indicate.     

A variable neighborhood search for graph coloring

Descent methods for combinatorial optimization proceed by performing a sequence of local changes on an initial solution which improve each time the value of an objective function until a local optimum is found. Several metaheuristics have been proposed which extend in various ways this scheme and avoid being trapped in local optima. For example, Hansen and Mladenovic have recently proposed the variable neighborhood search method which has not yet been applied to many combinatorial optimization problems. The aim of this paper is to propose an adaptation of this new method to the graph coloring problem.     

An edge coloring problem for graph products

The edges of the Cartesian product of graphs G × H are to be colored with the condition that all rectangles, i.e., K₂ × K₂ subgraphs, must be colored with four distinct colors. The minimum number of colors in such colorings is determined for all pairs of graphs except when G is 5-chromatic and H is 4- or 5-chromatic. © 1996 John Wiley & Sons, Inc.     

Concepts of signed graph coloring

This paper surveys recent development of concepts related to coloring of signed graphs. Various approaches are presented and discussed.     

Asymmetric directed graph coloring games

This note generalizes the (a,b)-coloring game and the (a,b)-marking game which were introduced by Kierstead [H.A. Kierstead, Asymmetric graph coloring games, J. Graph Theory 48 (2005) 169-185] for undirected graphs to directed graphs. We prove that the (a,b)-chromatic and (a,b)-coloring number for the class of orientations of forests is b+2 if b≤a, and infinity otherwise. From these results we deduce upper bounds for the (a,b)-coloring number of oriented outerplanar graphs and of orientations of graphs embeddable in a surface with bounded girth.