Скачать 73.9 Kb.

Keyword: graph coloring
In this paper we propose a method for integrating constraint propagation algorithms into an optimization procedure for vertex coloring with the goal of finding improved lower bounds. The key point we address is how to get instances of Constraint Satisfaction Problems (CSPs) from a graph coloring problem in order to give rise to new lower bounds outperforming the maximum clique bound. More precisely, the algorithms presented have the common goal of finding CSPs in the graph for which infeasibility can be proven. This is achieved by means of constraint propagation techniques which allow the algorithms to eliminate inconsistencies in the CSPs by updating domains dynamically and rendering such infeasibilities explicit. At the end of this process we use the largest CSP for which it has not been possible to prove infeasibility as an input for an algorithm which enlarges such CSP to get a feasible coloring. We experimented with a set of middlehigh density graphs with quite a large difference between the maximum clique and the chromatic number
In this paper we will describe a now class of coloring problems, arising from military frequency assignment, where we want to minimize the number of distinct nuples of colors used to color a given set of ncompletesubgraphs of a graph. We will propose two relaxations based on SemiDefinite Programming models for graph and hypergraph coloring, to approximate those (generally) NPhard problems, as well as a generalization of the works of Karger et al. for hypergraph coloring, to find good feasible solutions with a probabilistic approach.
The problem of kcoloring a graph is equivalent to deciding whether a particular cohomology class of a certain rational space vanishes. Although this problem is NPhard we are able to construct a fast (polynomial) algorithm to give. a representative of this class. We also associate to other classical decision problems rational spaces so that the given problem has a solution if and only if the associated space is not elliptic. As these spaces have null Euler homotopy characteristic we easily characterize when the given problem has a solution in terms of commutative algebra.
Suppose the graph G can be rcolored using colors 1,2,...,r, so that no vertex is adjacent to two vertices colored r. If P subset of V(G) is such that the distance between any two vertices in P is at least 12, then any rcoloring of P extends to an rcoloring of all of G. If there exists an rcoloring of G in which the distance between vertices colored r is at least 4 (resp. 6), then any rcoloring of P extends to an rcoloring of all of G provided the distance between any two vertices in P is at least 8 (resp. 6). Similar results hold if P induces a set of cliques. This continues previous work of the authors (Albertson and Moore, J. Combin. Theory Ser. B 77 (1999) 83.) on extending (r + 1)colorings of rchromatic graphs. Examples show that the distance constraints on P are almost sharp. We show that trianglefree outerplanar graphs instantiate our results and speculate on other families of graphs that might have rcolor extension theorems. (C) 2001 Elsevier Science B.V. All rights reserved.
An oriented kcoloring of an oriented graph G (that is a digraph with no cycle of length 2) is a partition of its vertex set into k subsets such that (i) no two adjacent vertices belong to the same subset and (ii) all the arcs between any two subsets have the same direction. We survey the main results that have been obtained on oriented graph colorings. (C) 2001 Elsevier Science B.V. All rights reserved
Improving a theorem of Gasarch and Hirst, we prove that if 2 less than or equal to k less than or equal to m less than or equal to omega, then the following is equivalent to WKL0 over RCA(0): Every locally kcolorable graph is mcolorable
This paper presents a heuristic graph coloring algorithm named MIPS_CLR, a MInimalstate Processing Search algorithm for the graph CoLoRing problem. Given a graph G(V, E), the goal of this NPcomplete problem is to find a color assignment to every vertex in II such that arty pair of adjacent vertices must not receive the same color but also the total number of colors should be minimized. The graph coloring problem has been widely studied due to its large number of practical applications in various fields. In MIPSCLR, a construction stage first generates an initial minimal state composed of as many as: colored vertices by a simple greedy algorithm, after a maximal clique of G is found by a maximum clique algorithm. Then, a refinement stage iteratively seeks a solution state while keeping minimality in terms of a cost function by a minimalstate transition method. In this method, the schemes of a best color selection, a random color selection, a color assignment shuffle, and a gradual color expansion are used together to realize the discrete descent starch with hillclimbing capabilities. The performance of MIPS_CLR is evaluated through solving DIMACS benchmark graph instances, where the solution quality is generally better than existing algorithms while the computation time is comparable with the Lest existing one. In particular, MIPSCLR provides new lower bound solutions for several instances. The simulation results, confirm the extensive search capability of our MIPS_CLR approach For the graph coloring problem
Graph coloring is a fundamental problem, which often appears in various scheduling problems like the file transfer problem on computer networks. In this paper, we survey recent advances and results oil the edgecoloring, the fcoloring, the [g,f]coloring, and the total coloring problem for various classes of graphs such as bipartite graphs, seriesparallel graphs, planar graphs, and graphs: having fixed degeneracy, treewidth, genus, arboricity, unicyclic index or thickness. In particular, we review various upper bounds on the minimum numbers of colors required to color these classes of graphs, and present efficient sequential and parallel algorithms to find colorings of graphs with these numbers of colors.
Suppose G is an schoosable graph with n vertices, and every vertex of G is assigned a list of t colors. We conjecture that at least (t/s)n of the vertices of G can be colored from these lists. We provide lower bounds and consider related questions. For instance, we show that if G is chicolorable (rather than being schoosable), then more than (1  ((chi  1)/chi)(t))n of the vertices of G can be colored from the lists and that this is asymptotically best possible. We include a number of open questions. (C) 2000 Elsevier Science B.V. All rights reserved
We prove that the game coloring number, and therefore the game chromatic number, of a planar graph is at most 18. This is a slight improvement of the current upper bound of 19. Perhaps more importantly, we bound the game coloring number of a graph G in terms of a new parameter, (G). We use this result to give very easy proofs of the best known upper bounds on game coloring number for forests, interval graphs, chordal graphs, outerplanar graphs, and line graphs and to give a new upper bound on the game coloring number of graphs embeddable on orientable surfaces with bounded genus. (C) 2000 Academic Press.
A recent and very promising approach for combinatorial optimization is to embed local search into the framework of evolutionary algorithms. In this paper, we present such hybrid algorithms for the graph coloring problem. These algorithms combine a new class of highly specialized crossover operators and a wellknown tabu search algorithm. Experiments of such a hybrid algorithm are carried out on large DIMACS Challenge benchmark graphs. Results prove very competitive with and even better than those of stateoftheart algorithms. Analysis of the behavior of the algorithm sheds light on ways to further improvement
The graph coloring problem is to color vertices of a graph so that no adjacent vertices are of the same color. The problem is difficult not only in finding the optimal solution, but also in approximation. Since it is hard to approximate the minimum number of colors, we consider to approximate the maximum number of unused colors. This approximation is based on saving colors with respect to the most naive coloring method, which colors each vertex with a different color. In this paper we propose a polynomialtime graph coloring algorithm with approximation ratio 3/4 for the maximum number of unused colors, which improves the previous result 2/3. (C) 1999 Elsevier Science Inc. All rights reserved.
This paper presents the results of an experimental investigation on solving graph coloring problems with Evolutionary Algorithms (EAs). After testing different algorithm variants we conclude that the best option is an asexual EA using orderbased representation and an adaptation mechanism that periodically changes the fitness function during the evolution. This adaptive EA is general, using no domain specific knowledge, except, of course, from the decoder (fitness function). We compare this adaptive EA to a powerful traditional graph coloring technique DSatur and the Grouping Genetic Algorithm (GGA) on a wide range of problem instances with different size, topology and edge density. The results show that the adaptive EA is superior to the Grouping (GA) and outperforms DSatur on the hardest problem instances. Furthermore, it scales up better with the problem size than the other two algorithms and indicates a linear computational complexity
The graph coloring problem is amongst the most difficult ones in combinatorial optimization, with a diverse set of significant applications in science and industry. Previous neural network attempts at coloring graphs have not worked well. In particular, they do not scale up to large graphs. Furthermore, experimental evaluations on realworld graphs have been lacking, and so have comparisons with state of the art conventional algorithms. In this paper we address all of these issues. We develop an improved neural network algorithm for graph coloring that scales well with graph size. The algorithm employs multiple restarts, and adaptively reduces the network's size from restart to restart as it learns better ways to color a given graph. Hence it gets faster and leaner as it evolves. We evaluate this algorithm on a structurally diverse set of graphs that arise in different applications. We compare its performance with that of a state of the art conventional algorithm on identical graphs. The conventional algorithm works better overall, though ours is not far behind. Ours works better on some graphs. The inherent parallel and distributed nature of our algorithm, especially within a neural network architecture, is a potential advantage for implementation and speed up.
Some genetic algorithms are considered for the graph coloring problem. As is the case for other combinatorial optimization problems, pure genetic algorithms are outperformed by neighborhood search heuristic procedures such as tabu search. Nevertheless, we examine the performance of several hybrid schemes that can obtain solutions of excellent quality. For some graphs, we illustrate that genetic operators can fulfill longterm strategic functions for a tabu search implementation that is chiefly founded on shortterm memory strategies.
The following graphcoloring result is proved: let G be a 2connected, bipartite, and plane graph. Then one can triangulate G in such a way that the resulting graph is 3colorable. Such a triangulation can be computed in O(n(2)) time. This result implies several new upper bounds for polygon guarding problems, including the first nontrivial upper bound for the rectilinear prison yard problem. (1) [n/3] vertex guards are sufficient to watch the interior of a rectilinear polygon with holes. (2) [5n/12] + 3 vertex guards ([n+4/3] point guards) are sufficient to simultaneously watch both the interior and exterior of a rectilinear polygon. Moreover, a new lower bound of [5n/16] vertex guards for the rectilinear prison yard problem is shown and proved to be asymptotically tight for the class of orthoconvex polygons
Given a graph G (or more generally a matroid embedded in a projective space), we construct a sequence of algebraic varieties whose geometry encodes combinatorial information about G. For example, the chromatic polynomial of G can be computed as an intersection product of certain classes on these varieties, or recovered in terms of the Segre classes of related subschemes of P ''; other information such as Crape's invariant also finds a very natural geometric counterpart. The note presents this construction, and gives 'geometric' proofs of a number of standard combinatorial results on the chromatic polynomial and Crape's invariant
This note is a report of testing a straightforward generalization of the randomized 3coloring algorithm of Petford and Welsh (1989) on the decision problems of 4 and 10coloring. We observe similar behavior, namely the existence of critical regions. Experimentally, the average time complexity for large n again seems to grow slowly, although in some cases the number of transitions needed is prohibitively high for practical applications.
We analyse the problem of executing periodic operations on a minimum number of identical processors under different constraints. The analysis is based on a reformulation of the problem in terms of graph colouring. It is shown that different constraints result in colouring problems defined on different classes of graphs, viz. interval graphs, circulararc graphs and periodicinterval graphs. We discuss the complexity of these colouring problems in detail. Web of Science Keyword: Graph coloring References 2002
This paper gives new constructions of kchromatic critical graphs with high minimum degree and high edge density, and of vertexcritical graphs with high edge density
A graph G is kdivisible if for each induced subgraph H of G with at least one edge, there is a partition of the vertex set of H into sets V_{1},...,V_{k} such that no V_{i} contains a maximum clique of H. We show that a clawfree graph is 2divisible if and only if it does not contain an odd hole: we conjecture that this result is true for any graph, and present further conjectures relating 2divisibility to the strong perfect graph conjecture. We also present related results involving the chromatic number and the stability number, with connections to Ramsey theory 2001
Suppose the graph G can be rcolored using colors 1,2,...,r, so that no vertex is adjacent to two vertices colored r. If PV(G) is such that the distance between any two vertices in P is at least 12, then any rcoloring of P extends to an rcoloring of all of G. If there exists an rcoloring of G in which the distance between vertices colored r is at least 4 (resp. 6), then any rcoloring of P extends to an rcoloring of all of G provided the distance between any two vertices in P is at least 8 (resp. 6). Similar results hold if P induces a set of cliques. This continues previous work of the authors (Albertson and Moore, J. Combin. Theory Ser. B 77 (1999) 83.) on extending (r+1)colorings of rchromatic graphs. Examples show that the distance constraints on P are almost sharp. We show that trianglefree outerplanar graphs instantiate our results and speculate on other families of graphs that might have rcolor extension theorems
An oriented kcoloring of an oriented graph G (that is a digraph with no cycle of length 2) is a partition of its vertex set into k subsets such that (i) no two adjacent vertices belong to the same subset and (ii) all the arcs between any two subsets have the same direction. We survey the main results that have been obtained on oriented graph colorings. 2000
In this paper, it is shown that if the maximum degree of a graph is large relative to the genus of the embedding than the edgeface chromatic number of the graph is at most +1 and its vertexedgeface chromatic number is at most +2. Both results are best possible
Consider the parameter for a kchromatic graph G, on the set of vertices V(G) and with the set of edges E(G). It is known that (G)0 for any kchromatic uniquely vertexcolourable graph G (kUCG), and, S.J. Xu has conjectured that for any kUCG, G, (G)=0 implies that cl(G)=k; in which cl(G) is the clique number of G. In this paper, first, we introduce the concept of the core of a kUCG as an induced subgraph without any colourclass of size one, and without any vertex of degree k1. Considering (k,n)cores as kUCGs on n vertices, we show that edgeminimal (k,2k)cores do not exist when k3, which shows that for any edgeminimal kUCG on 2k vertices either the conjecture is true or there exists a colourclass of size one. Also, we consider the structure of edgeminimal (k,2k+1)cores and we show that such cores exist for all k4. Moreover, we characterize all edgeminimal (4,9)cores and we show that there are only seven such cores (up to isomorphism). Our proof shows that Xu's conjecture is true in the case of edgeminimal (4,9)cores
We introduce the concept of variable degeneracy of a graph extending that of kdegeneracy. This makes it possible to give a common generalization of the point partition numbers and the list chromatic number. In particular, the list point arboricity of a graph is considered. We extend Brooks' and Gallai's theorems in terms of covering the vertices of a graph by disjoint induced subgraphs G_{1},...,G_{s} such that G_{i} is strictly f_{i}degenerate, given nonnegativeintegervalued functions f_{1},...,f_{s} whose sum is bounded below at each vertex by the degree of that vertex. 