The goal of this thesis is to study the evolution and robustness of some graph parameters when faced with attacks.
The chromatic number of a graph is one of the most studied parameters in graph theory: the goal is to find the smallest number of colors with which we can color every vertex of a graph such that no two adjacent vertices have the same color. A natural algorithm is to select the vertices in a certain order and to color each of them with the smallest available color. This does not always give us the best coloring, since the problem is NP-complete, but we know that there exists an ordering leading to an optimal coloring. An ordering can also lead to poor colorings, and the Grundy number of a graph is the number of colors reached in the worst-case ordering. Another way to see this parameter is to consider that an attacker gives us vertices in a certain order such that we need a great number of colors. The Grundy number ensures us that we will not need more that its value.
There are other ways to construct a graph coloring with an opponent, such as the game graph coloring, defined by Bodlaender in the 1990s. In this problem, Alice and Bob properly color a vertex of a graph each turn, with different goals: Alice must color the whole graph, while Bob must prevent her to do so. The game coloring number is the smallest number of colors with which Alice has a winning strategy. This kind of game is currently the subject of many studies, and many variants have been defined using other known problems of graph theory as a basis. Those games can be a good model for security problems in networks, where Bob is the attacker wanting to break the stability of a system (Alice wanting to guarantee said stability).
In a first time, the student will have to study the existing results in Grundy coloring, game coloring and other variants such as Grundy game coloring. Improving the known bounds on existing parameters on certain classes of graphs, such as planar graphs, interval graphs, power graphs or regular graphs, is expected. Other variants of Grundy coloring will be studied, such as partial Grundy coloring, where the Grundy property is satisfied for only a subset of the graph vertices. In particular, a study of the extremal cases will be led, in order to characterize the graphs for which the known bounds of those parameters are reached.
For the next part of the thesis, those first works and a good knowledge of the state of the art will allow to study other parameters of graphs under the same aspects. Recently, this has been the case for the dominating game number or the adaptative identifying codes. Many questions remain open with the introduction of those notions.
The expected results for this thesis are the following:
- theoritical algorithmic complexity of the computation of Grundy or game parameters.
- computation of the exact values of Grundy or game parameters for some classes of graphs.
- adaptation of known results on graph coloring/domination in attacked version.