On a parallel genetic–tabu search based algorithm for solving the graph colouring problem

In this paper, we are interested in a particular combinatorial optimisation problem (COP), namely the graph colouring problem (GCP). To solve the GCP, we present a parallel approach adopting an efficient strategy. A brief survey on known methods for solving the GCP enables us to justify our approach which is based on a hybrid method, starting from a set of solutions initialized by the so-called RLF colouring method and combining both a genetic algorithm and the tabu search. A parallelising strategy is then applied. The performances of our method were evaluated through a series of experimentations achieved on an IBM SP2 multiprocessor. The processed graphs were chosen from two benchmark sets. The first, taken from the Internet, involves graphs whose chromatic numbers are known and the second involves random generated graphs. The analysis of the results proves the interest of our approach.     

Colouring games based on autotopisms of Latin hyper-rectangles

Abstract

Every partial colouring of a Hamming graph is uniquely related to a partial Latin hyper-rectangle. In this paper we introduce the Θ-stabilized (a, b)-colouring game for Hamming graphs, a variant of the (a, b)-colouring game so that each move must respect a given autotopism Θ of the resulting partial Latin hyperrectangle. We examine the complexity of this variant by means of its chromatic number. We focus in particular on the bi-dimensional case, for which the game is played on the Cartesian product of two complete graphs, and also on the hypercube case.     

The Proportional Colouring Problem: Optimizing Buffers in Wireless Mesh Networks

In this paper, we consider a new edge colouring problem motivated by wireless mesh networks optimization: the proportional edge colouring problem. Given a graph G with positive weights associated to its edges, we want to find a proper edge colouring which assigns to each edge at least a proportion (given by its weight) of all the colours. If such colouring exists, we want to find one using the minimum number of colours. We proved that deciding if a weighted graph admits a proportional edge colouring is polynomial while determining its proportional edge chromatic number is NP-hard. We also give a lower and an upper bound that can be polynomially computed. We finally characterize some graphs and weighted graphs for which we can determine the proportional edge chromatic number.     

Tackling the edge dynamic graph colouring problem with and without future adjacency information

Many real world operational research problems, such as frequency assignment and exam timetabling, can be reformulated as graph colouring problems (GCPs). Most algorithms for the GCP operate under the assumption that its constraints are fixed, allowing us to model the problem using a static graph. However, in many real-world cases this does not hold and it is more appropriate to model problems with constraints that change over time using an edge dynamic graph. Although exploring methods for colouring dynamic graphs has been identified as an area of interest with many real-world applications, to date, very little literature exists regarding such methods. In this paper we present several heuristic methods for modifying a feasible colouring at time-step t into an initial, but not necessarily feasible, colouring for a “similar” graph at time-step \(t+1\). We will discuss two cases; (1) where changes occur at random, and (2) where probabilistic information about future changes is provided. Experimental results are also presented and the benefits of applying these particular modification methods are investigated.     

A Bayesian Game without ∈-equilibria

We present a three-player Bayesian game for which there are no ∈-equilibria in Borel measurable strategies for small enough positive ∈, however there are non-measurable equilibria. The structure of the game employs a nonamenable semi-group action corresponding to the knowledge of the players. The equilibrium property is related to the proper colouring of graphs and the Borel chromatic number; but rather than keeping adjacent vertices coloured differently there are algebraic conditions relating to the topology of the space and some ergodic operators.     

On improper interval edge colourings

We study improper interval edge colourings, defined by the requirement that the edge colours around each vertex form an integer interval. For the corresponding chromatic invariant (being the maximum number of colours in such a colouring), we present upper and lower bounds and discuss their qualities; also, we determine its values and estimates for graphs of various families, like wheels, prisms or complete graphs. The study of this parameter was inspired by the interval colouring, introduced by Asratian, Kamalian (1987). The difference is that we relax the requirement on the original colouring to be proper.     

Approximating the minimum clique cover and other hard problems in subtree filament graphs

Subtree filament graphs are the intersection graphs of subtree filaments in a tree. This class of graphs contains subtree overlap graphs, interval filament graphs, chordal graphs, circle graphs, circular-arc graphs, cocomparability graphs, and polygon-circle graphs. In this paper we show that, for circle graphs, the clique cover problem is NP-complete and the h-clique cover problem for fixed h is solvable in polynomial time. We then present a general scheme for developing approximation algorithms for subtree filament graphs, and give approximation algorithms developed from the scheme for the following problems which are NP-complete on circle graphs and therefore on subtree filament graphs: clique cover, vertex colouring, maximum k-colourable subgraph, and maximum h-coverable subgraph.     

Infinite quantum graphs

Infinite quantum graphs with δ-interactions at vertices are studied without any assumptions on the lengths of edges of the underlying metric graphs. A connection between spectral properties of a quantum graph and a certain discrete Laplacian given on a graph with infinitely many vertices and edges is established. In particular, it is shown that these operators are self-adjoint, lower semibounded, nonnegative, discrete, etc. only simultaneously.     

Generalization of Achromatic Colouring of Central Graphs

In this paper we discuss the achromatic coloring of graphs, and the achromatic number of central graph of Wheel graphs and Gear graphs and generalize the achromatic colouring of central graphs.     

A unified approach to distance-two colouring of graphs on surfaces

In this paper we introduce the notion of Σ-colouring of a graph G: For given subsets Σ(v) of neighbours of v, for every v∈V (G), this is a proper colouring of the vertices of G such that, in addition, vertices that appear together in some Σ(v) receive different colours. This concept generalises the notion of colouring the square of graphs and of cyclic colouring of graphs embedded in a surface. We prove a general result for graphs embeddable in a fixed surface, which implies asymptotic versions of Wegner’s and Borodin’s Conjecture on the planar version of these two colourings. Using a recent approach of Havet et al., we reduce the problem to edge-colouring of multigraphs, and then use Kahn’s result that the list chromatic index is close to the fractional chromatic index. Our results are based on a strong structural lemma for graphs embeddable in a fixed surface, which also implies that the size of a clique in the square of a graph of maximum degree Δ embeddable in some fixed surface is at most $ \frac{3} {2}\Delta $ plus a constant.     

Halin图的点着色算法

本文解决了Halin图的点色数问题,并给出了一个可在线性时间内对Halin图进行点着色的算法。     

Symmetry Groups of Coloured Graphs

A perfect colouring Φ of a simple undirected connected graph G is an edge colouring such that each vertex is incident with exactly one edge of each colour. This paper concerns the problem of representing groups by graphs with perfect colourings. We define groups of graph automorphisms, which preserve the structure of the colouring, and characterize these groups up to isomorphism. Our considerations are based on the fact that every perfectly coloured graph is isomorphic to a Schreier coset graph on a group generated by involutions.     

图全染色的几个定理

图的全染色是染色理论的重要内容 ,全染色猜想 :设 G是一个简单图 ,则 XT( G)≤△ ( G) +2是一个至今未解决的问题 .本文证明了对于一些图类全染色猜想是正确的 .     

Representing Groups by Colourings of Graphs

The topic of this paper is representing groups by edge-coloured graphs. Every edge-coloured graph determines a group of graph automorphisms which preserve the colours of the edges. An edge colouring of a graph G is called a perfect one iff every colour class is a perfect matching in G. We prove that every group H and all of its subgroups can be represented (up to isomorphism) by a group of colour preserving automorphisms related to some perfect colouring of the same graph.     

Convex Entire Noncommutative Functions are Polynomials of Degree Two or Less

We establish several new relations between the discrete transition operator, the continuous Laplacian and the averaging operator associated with combinatorial and metric graphs. It is shown that these operators can be expressed through each other in a very explicit way. In particular, the averaging operator appears to be closely related to the solutions of the associated wave equation. The machinery used allows one to study a class of infinite graphs without assumption on the local finiteness.     

Remarks on waveform relaxation method with overlapping splittings

By studying the superlinear convergence of waveform relaxation method on finite time intervals, it has formerly been shown, by using the theory of quasinilpotent operators, that the convergence properties are largely determined by the graph properties of the splitting. In this paper, we show how the directed graphs associated to the decomposition are modified when overlapping splittings are used. In particular, we explain how overlapping should be used in order to best accelerate convergence of the iteration method.     

Graphs of linear operators

In 2006 the author proposed an algorithm for constructing graphs of difference operators. In this paper, the following question is studied: to which linear operators $ \mathcal{A} In 2006 the author proposed an algorithm for constructing graphs of difference operators. In this paper, the following question is studied: to which linear operators does this algorithm apply? Graphs of difference operators are used to determine the complexity of a sequence in the sense of Arnold, so the algorithm makes it possible to determine the complexity of any sequence. Original Russian Text ? A.I. Garber, 2008, published in Trudy Matematicheskogo Instituta imeni V.A. Steklova, 2008, Vol. 263, pp. 64–71.