An evolutionary approach for bandwidth multicoloring problems

In this paper we consider some generalizations of the vertex coloring problem, where distance constraints are imposed between adjacent vertices (bandwidth coloring problem) and each vertex has to be colored with more than one color (bandwidth multicoloring problem). We propose an evolutionary metaheuristic approach for the first problem, combining an effective tabu search algorithm with population management procedures. The approach can be applied to the second problem as well, after a simple transformation. Computational results on instances from the literature show that the overall algorithm is able to produce high quality solutions in a reasonable amount of time, outperforming the most effective algorithms proposed for the bandwidth coloring problem, and improving the best known solution of many instances of the bandwidth multicoloring problem.     

Halin-图的点强全染色

图G(V,E)的一个k-正常全染色f叫做一个k-点强全染色当且仅当对任意v∈V(G), N[v]中的元素被染不同色,其中N[v]={u|uv∈V(G)}∪{v}．χTvs(G)=min{k|存在图G的k- 点强全染色}叫做图G的点强全色数．对3-连通平面图G(V,E),如果删去面fo边界上的所有点后的图为一个树图,则G(V,E)叫做一个Halin-图．本文确定了最大度不小于6的Halin- 图和一些特殊图的的点强全色数XTvs(G),并提出了如下猜想:设G(V,E)为每一连通分支的阶不小于6的图,则χTvs(G)≤△(G) 2,其中△(G)为图G(V,E)的最大度．     

Coloring graphs by iterated local search traversing feasible and infeasible solutions

Graph coloring is one of the hardest combinatorial optimization problems for which a wide variety of algorithms has been proposed over the last 30 years. The problem is as follows: given a graph one has to assign a label to each vertex such that no monochromatic edge appears and the number of different labels used is minimized. In this paper we present a new heuristic for this problem which works with two different functionalities. One is defined by two greedy subroutines, the former being a greedy constructive one and the other a greedy modification one. The other functionality is a perturbation subroutine, which can produce also infeasible colorings, and the ability is then to retrieve feasible solutions. In our experimentation the proper tuning of this optimization scheme produced good results on known graph coloring benchmarks.     

棋盘图的几种染色

染色问题是图论的重要研究内容之一,采用一种全新的方法给出了一类特殊图——棋盘图的邻点可区别边染色和邻点可区别全染色,并给出了相应的色数.     

A GRASP for Coloring Sparse Graphs

We first present a literature review of heuristics and metaheuristics developed for the problem of coloring graphs. We then present a Greedy Randomized Adaptive Search Procedure (GRASP) for coloring sparse graphs. The procedure is tested on graphs of known chromatic number, as well as random graphs with edge probability 0.1 having from 50 to 500 vertices. Empirical results indicate that the proposed GRASP implementation compares favorably to classical heuristics and implementations of simulated annealing and tabu search. GRASP is also found to be competitive with a genetic algorithm that is considered one of the best currently available for graph coloring.     

Graph coloring in the estimation of sparse derivative matrices: Instances and applications

We describe a graph coloring problem associated with the determination of mathematical derivatives. The coloring instances are obtained as intersection graphs of row partitioned sparse derivative matrices. The size of the graph is dependent on the partition and can be varied between the number of columns and the number of nonzero entries. If solved exactly our proposal will yield a significant reduction in computational cost of the derivative matrices. The effectiveness of our approach is demonstrated via a practical problem from computational molecular biology. We also remark on the hardness of the generated coloring instances.     

A short proof of the NP-completeness of minimum sum interval coloring

In the minimum sum coloring problem we have to assign positive integers to the vertices of a graph in such a way that neighbors receive different numbers and the sum of the numbers is minimized. Szkalicki has shown that minimum sum coloring is NP-hard for interval graphs. Here we present a simpler proof of this result.     

The graph coloring problem: A neuronal network approach

Solution of an optimization problem with linear constraints through the continuous Hopfield network (CHN) is based on an energy or Lyapunov function that decreases as the system evolves until a local minimum value is attained. This approach is extended in to optimization problems with quadratic constraints. As a particular case, the graph coloring problem (GCP) is analyzed. The mapping procedure and an appropriate parameter-setting procedure are detailed. To test the theoretical results, some computational experiments solving the GCP are shown.     

Path problems in generalized stars, complete graphs, and brick wall graphs

Path problems such as the maximum edge-disjoint paths problem, the path coloring problem, and the maximum path coloring problem are relevant for resource allocation in communication networks, in particular all-optical networks. In this paper, it is shown that maximum path coloring can be solved optimally in polynomial time for bidirected generalized stars, even in the weighted case. Furthermore, the maximum edge-disjoint paths problem is proved NP-hard for complete graphs (undirected or bidirected), a constant-factor off-line approximation algorithm is presented for the weighted case, and an on-line algorithm with constant competitive ratio is given for the unweighted case. Finally, an open problem concerning the existence of routings that simultaneously minimize the maximum load and the number of colors is solved: an example for a graph and a set of requests is given such that any routing that minimizes the maximum load requires strictly more colors for path coloring than a routing that minimizes the number of colors.     

NP‐completeness of list coloring and precoloring extension on the edges of planar graphs

In the edge precoloring extension problem, we are given a graph with some of the edges having preassigned colors and it has to be decided whether this coloring can be extended to a proper k‐edge‐coloring of the graph. In list edge coloring every edge has a list of admissible colors, and the question is whether there is a proper edge coloring where every edge receives a color from its list. We show that both problems are NP‐complete on (a) planar 3‐regular bipartite graphs, (b) bipartite outerplanar graphs, and (c) bipartite series‐parallel graphs. This improves previous results of Easton and Parker 6 , and Fiala 8 . © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 313–324, 2005     

Facets of the Graph Coloring Polytope

In this paper we present a study of the polytope associated to a classic linear integer programming formulation of the graph coloring problem. We determine some families of facets. This is the initial step for the development of a branch-and-cut algorithm to solve large instances of the graph coloring problem.     

Minimum sum edge colorings of multicycles

In the minimum sum edge coloring problem, we aim to assign natural numbers to edges of a graph, so that adjacent edges receive different numbers, and the sum of the numbers assigned to the edges is minimum. The chromatic edge strength of a graph is the minimum number of colors required in a minimum sum edge coloring of this graph. We study the case of multicycles, defined as cycles with parallel edges, and give a closed-form expression for the chromatic edge strength of a multicycle, thereby extending a theorem due to Berge. It is shown that the minimum sum can be achieved with a number of colors equal to the chromatic index. We also propose simple algorithms for finding a minimum sum edge coloring of a multicycle. Finally, these results are generalized to a large family of minimum cost coloring problems.     

Quantum annealing of the graph coloring problem

Quantum annealing extends simulated annealing by introducing artificial quantum fluctuations. The path-integral Monte Carlo version chosen is population-based and designed to be implemented on a classical computer. Its first application to the graph coloring problem is presented in this paper. It is shown by experiments that quantum annealing can outperform classical thermal simulated annealing for this particular problem. Moreover, quantum annealing proved competitive when compared with the best algorithms on most of the difficult instances from the DIMACS benchmarks. The quantum annealing algorithm has even found that the well-known benchmark graph dsjc1000.9 has a chromatic number of at most 222. This is an improvement on its best upper-bound from a large body of literature.     

The harmonious coloring problem is NP-complete for interval and permutation graphs

In this paper, we prove that the harmonious coloring problem is NP-complete for connected interval and permutation graphs. Given a simple graph G, a harmonious coloring of G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number is the least integer k for which G admits a harmonious coloring with k colors. Extending previous work on the NP-completeness of the harmonious coloring problem when restricted to the class of disconnected graphs which are simultaneously cographs and interval graphs, we prove that the problem is also NP-complete for connected interval and permutation graphs.     

An Unconstrained Quadratic Binary Programming Approach to the Vertex Coloring Problem

The vertex coloring problem has been the subject of extensive research for many years. Driven by application potential as well as computational challenge, a variety of methods have been proposed for this difficult class of problems. Recent successes in the use of the unconstrained quadratic programming (UQP) model as a unified framework for modeling and solving combinatorial optimization problems have motivated a new approach to the vertex coloring problem. In this paper we present a UQP approach to this problem and illustrate its attractiveness with preliminary computational experience.     

Rainbows in the Hypercube

Let Q_n be a hypercube of dimension n, that is, a graph whose vertices are binary n-tuples and two vertices are adjacent iff the corresponding n-tuples differ in exactly one position. An edge coloring of a graph H is called rainbow if no two edges of H have the same color. Let f(G,H) be the largest number of colors such that there exists an edge coloring of G with f(G,H) colors such that no subgraph isomorphic to H is rainbow. In this paper we start the investigation of this anti-Ramsey problem by providing bounds on f(Q_n,Q_k) which are asymptotically tight for k = 2 and by giving some exact results.     

路与圈图的联图的均匀强边染色

For a proper edge coloring c of a graph G,if the sets of colors of adjacent vertices are distinct,the edge coloring c is called an adjacent strong edge coloring of G.Let c i be the number of edges colored by i.If |c i c j | ≤ 1 for any two colors i and j,then c is an equitable edge coloring of G.The coloring c is an equitable adjacent strong edge coloring of G if it is both adjacent strong edge coloring and equitable edge coloring.The least number of colors of such a coloring c is called the equitable adjacent strong chromatic index of G.In this paper,we determine the equitable adjacent strong chromatic index of the joins of paths and cycles.Precisely,we show that the equitable adjacent strong chromatic index of the joins of paths and cycles is equal to the maximum degree plus one or two.     

Optimal shift coloring of trees

This paper was motivated by the problem of scheduling the openings of pharmacies during week-ends and holiday periods (shifts). The problem can be modeled as a coloring problem on a graph. In this paper we focus on the special case where the underlying graph is a tree, or, more generally, it is endowed with a tree-metric, and we provide a polynomial-time algorithm. We also provide direct optimal solutions for special trees like stars and paths.     

Notes应用程序中角色组合的最少策略

在Ｎｏｔｅｓ 应用程序设计过程中,角色的分配合一直是一个容易被忽略的问题．本文将此问题提炼为一个数学模型,并用图论中已有的顶点染色法解决,得出了较为合理的算法和结果．     

Complexity of the packing coloring problem for trees

Packing coloring is a partitioning of the vertex set of a graph with the property that vertices in the i-th class have pairwise distance greater than i. The main result of this paper is a solution of an open problem of Goddard et al. showing that the decision whether a tree allows a packing coloring with at most k classes is NP-complete.We further discuss specific cases when this problem allows an efficient algorithm. Namely, we show that it is decideable in polynomial time for graphs of bounded treewidth and diameter, and fixed parameter tractable for chordal graphs.We accompany these results by several observations on a closely related variant of the packing coloring problem, where the lower bounds on the distances between vertices inside color classes are determined by an infinite nondecreasing sequence of bounded integers.