**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Personne# Ivo Blöchliger

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Unités associées

Chargement

Cours enseignés par cette personne

Chargement

Domaines de recherche associés

Chargement

Publications associées

Chargement

Personnes menant des recherches similaires

Chargement

Cours enseignés par cette personne

Aucun résultat

Personnes menant des recherches similaires (4)

Unités associées (1)

Domaines de recherche associés (1)

Coloration de graphe

thumb|Une coloration du graphe de Petersen avec 3 couleurs.
En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés

Publications associées (9)

Chargement

Chargement

Chargement

Ivo Blöchliger, Daniela Bronner

We consider vertex k-colorings of an arbitrary simple, connected, and undirected graph G=(V,E) such that, for every vertex v, at most lambda different colors occur in the closed neighborhood of v. These colorings are called (k,lambda)-colorings. If a graph has a (k,lambda)-coloring with lambda < chi we say that the graph is oligomatic. We present some results concerning universal graphs U(k,lambda) which are generic (in a sense to be defined) (k,lambda)-colorable graphs. We determine the chromatic number chi of all U(k,lambda) with k==2. We also show that there is no claw-free graph admitting a (chi+1, chi-1)-coloring, that there is no line graph admitting a (k,chi-2)-coloring and that there is no oligomatic Halin graph.

2006Graph Coloring is a very active field of research in graph theory as well as in the domain of the design of efficient heuristics to solve problems which, due to their computational complexity, cannot be solved exactly (no guarantee that an optimal solution will be reported), see [Cul] for a list of over 450 references. The graph coloring problem involves coloring the vertices of a given graph in such a way that two adjacent vertices never share the same color. The goal is to find the smallest number of colors needed to color all vertices in a fashion that satisfies this requirement. This number is called chromatic number and is denoted by Χ. In the first chapter, we present our research on suboptimal colorings and graphs which can be colored in such a way that the number of different colors appearing on the closed neighborhood (a vertex plus its neighbors) of any vertex v is less than Χ. We call such graphs oligomatic. The most interesting result is the following: given a graph and a coloring using Χ + p colors, there exists a vertex v such that there are at least Χ different colors among all vertices which are at a distance of [p/2] + 1 or less from v. We also study the existence of oligomatic graphs in special classes. Additionally, we present results of research on universal graphs which are "generic" oligomatic graphs in the sense that most properties of oligomatic graphs can be analyzed by restricting ourselves to universal graphs. Chapters Two to Four deal with the development of heuristics for two types of graph coloring problems. The tabu search heuristic was a central focus of our research. A tabu search iteratively modifies a candidate solution (which becomes the new candidate solution) with the goal of improving it. In such a procedure it is forbidden (tabu) to undo a modification for a certain number iterations. This mechanism allows to escape from local minima. In Chapter Two, we propose general improvements for tabu search based on some new and simple mechanisms (called reactive tabu schemes) to adapt the tabu tenure (which corresponds to the number of iterations a modification stays tabu). We also introduce distance and similarity measures for graph coloring problems which are needed in iterative procedures such as those of the tabu search. In the third chapter, we present the PARTIALCOL heuristic for the graph coloring problem. This method obtains excellent results compared to other similar methods and is able to color the well known DIMACS [JT96] benchmark graph flat300_28_0 optimally with 28 colors. (The best colorings found to date by other researchers use at least 31 colors.) PARTIALCOL uses partial solutions in its search space, which is a little explored way of approaching the graph coloring problem. Most approaches either use colorings and try to minimize the number of colors, or they use improper colorings (having conflicts, i.e. adjacent vertices which may have the same color) and try to minimize the number of conflicts. In the final chapter, we present a weighted version of the graph coloring problem which has applications in batch scheduling and telecommunication problems. We present two different adaptations of tabu search to the weighted graph coloring problem and test several of the reactive tabu schemes presented in Chapter Two. Further, we devise an adaptive memory algorithm AMA inspired by genetic algorithms. A large set of benchmark graphs with different properties is presented. All benchmark graphs with known optima have been solved to optimality by AMA. A key element of this algorithm is its capacity to determine the number k of colors to be used. Most other graph coloring heuristics need this parameter to be supplied by the user. Considering the results obtained on various graphs, we are confident that the methods developed are very efficient.