A graph invariant is a function that associates to each graph a numerical value that is independant from the labelling of its vertices and edges. The Randic index is a graph invariant well studied in chemical graph theory for its relation to properties of a chemical compound such as the boiling point. The present research focusses on chemical graphs, i.e., graphs with maximum degree 4, and aims at characterizing critical edges (edges whose removal leads to a modification of the value of a given invariant) for the Randic index. Using new features of AutoGraphiX 2, conditions to characterize edges whose removal leads to a rise respectively to a decrease of the Randic index are studied as well as the graphs for which the number of critical edges is maximum.

The maximum stable set problem is known to be NP-hard even when restricted to many classes characterized by forbidden induced subgraphs. On the other hand, there are some cases which are known to be polynomially solvable. The best known is the case of line graphs, which is equivalent to the maximum matching problem in all graphs. The corresponding algorithm manages to detect alternating chains for augmenting the current matching, or to prove that there are no such chains. This result has been generalized later to claw-free graphs, using a similar technique, namely the augmenting graphs technique. In this talk we provide a method to detect augmenting chains in generalizations of claw-free graphs. As a consquence, the maxiumum stable set problem can be solved in a larger hereditary class.

Edge-Reversal dynamics have recently been used to try to color the vertices of a graph using the minimum number of colors, with good results. Bichromatic exchanges have also been used efficiently to mutate a feasible solution into a different solution, without deteriorating its quality. We study an algorithm that combines these two concepts in order to gain both the quality of results from edge-reversal and the convergence properties of bichromatic exchanges.