Three years of graphs and music : some results in graph theory and its applications
Nathann Cohen · HAL (Le Centre pour la Communication Scientifique Directe) · 2011
This thesis consists in successive glimpses of different problems in discrete mathematics related to graph theory. Its mains focus is on graph colouring, i.e. on assignments of integer values to the vertices (or edges) of a graph satisfying a set of local constraints, most of the time the exclusion of specific patterns in the coloured graph. For several different types of colouring (vertex and edge choosability, acyclic or linear colouring, ...) a state of the art is provided, along with results ensuring the existence of such colourings on planar graphs or subclasses of them -- with the aim of minimising the number of colours used for a given Maximum Degree, or Maximum Average Degree. This thesis also deals with decompositions of graphs into induced subgraphs, and asserts that similarly to what Wilson's theorem implies for non-induced graph decomposition, there exists for any graph $H$ an infinite sequence of dense graph whose edge set can be partitioned in induced copies of $H$. The proof methodology involves hypergraphs, for which a decomposition result is presented, i.e. that the complete 3-uniform hypergraph can be partitioned into $\lceil \frac {n(n-1)} 6\rceil$ $\alpha$-acyclic hypergraphs as conjectured. In a third part are gathered algorithmic questions. Those are problems of optimisation or existence motivated by telecommunications in networks, studied with the classical framework of computational complexity, or the search of subgraphs through parametrised complexity. In a fourth part it, considers counting problems belonging to the study of chemical graphs, and finally details some Integer LinearPrograms used in the Mathematics software Sage.