Tag: graphs
Beyond the fractional Reed bound for triangle-free graphs
summary: The notion of fractional colouring is an important concept in graph theory that is commonly used to extend the notion of graph colouring beyond integer values. It is a relaxation of the traditional chromatic number, allowing for real-valued weights or probabilities associated with each independent set of a graph ...
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 ...
The structure of quasi-transitive graphs avoiding a minor with applications to the Domino Conjecture.:00
summary: An infinite graph is quasi-transitive if its automorphism group has finitely many orbits. In this talk, I will present a structure theorem for locally finite quasi-transitive graphs avoiding a minor, which is reminiscent of the Robertson-Seymour Graph Minor Structure Theorem. We prove that every locally finite quasi-transitive graph G ...
Algorithms for the Metric Dimension problem on directed graphs
summary: In graph theory, the Metric Dimension problem is the following: we are looking for a minimum-size set R of vertices, such that for any pair of vertices of the graph, there is a vertex from R whose two distances to the vertices of the pair are distinct. This problem ...
Designing truthful mecanism
summary: In this presentation, we will focus on the generalization of knapsack budgeting. Given a set of projects and a budget, each voter selects a subset of projects; we want to maximize social welfare. Different measures can describe this (maximizing the minimum utility of the players, maximizing the sum of ...
Classification of truth revealing social choice algorithms
summary: The talk will be on the field of social choices. A group of players want to choose a subset of a set of objects respecting some properties (maximal weight of the subset, maximal amount of objects in the subset, ...). To do so, they vote and use a social choice ...
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 ...
Self-Stabilization and Byzantine Tolerance for Maximal Independent Set
summary: We analyze the impact of transient and Byzantine faults on the construction of a maximal independent set in a general network. We adapt the self-stabilizing algorithm presented by Turau for computing such a vertex set. Our algorithm is self-stabilizing, and also works under the more difficult context of arbitrary ...
A counting argument for graph colouring
summary: In 2010, Moser and Tardos introduced an algorithmic version of the celebrated Lovász Local Lemma using the entropy compression method. Their method is now widely used in the community and has become a standard of the probabilistic method, mainly because it often provides the tightest existential bounds. However, it ...
L-orientations of graphs
summary: An orientation of an (undirected) graph G is an assignment of directions to each edge of G. In this talk, we consider an orientation such that the out-degree of each vertex is contained in a given list. We introduce several relations to graph theory topics and pose our main ...