Articles by Quentin Chuet
Variations sur le problème de coloration de graphes
summary: Le problème de coloration propre est un sujet fondamental en théorie des graphes; non seulement les colorations propres présentent une complexité fascinante en tant qu'objets combinatoires, mais elles apparaissent également dans un large éventail d'applications, notamment parmi les problèmes d'allocation de ressources. Cependant, certaines applications spécifiques ...
Proper conflict-free colourings of graphs
summary: Given a graph \(G\) of maximum degree \(\Delta\), the proper colouring problem asks for the minimum number of colours that can be assigned to the vertices of \(G\) such that no pair of adjacent vertices are given the same colour; it is easy to show that at most \(\Delta ...
Graph colourings, subcolourings, and beyond
summary: The graph colouring problem is central in Graph Theory: it consists in colouring the vertices of a graph such that each colour class induces an independent set, using as few colours as possible. While very difficult to solve exactly, the problem and its worst cases are now understood quite ...
Acyclic colorings of graphs and the probabilistic method
summary: Graph colorings have been extensively studied for the past century, due to the richness of the theory and its numerous applications. Part of the current research focuses on constrained colorings, and how their properties differ from proper colorings. When we require that, in a proper coloring, no (even) cycle ...