Tag: graphs
Edge k-q-colorability of graphs
summary: Given positive integers k, q, we say that a graph is edge k-q-colorable if its edges can be colored in such a way that the number of colors incident to each vertex is at most q and that the size of a largest color class is at most k ...
The freezing threshold for uniformly random colourings of sparse graphs
summary: Given a random Δ-regular graph G, it holds that χ(G) ~ Δ / (2 ln Δ) with high probability. However, for any ε > 0 and k large enough, no (randomised) polynomial-time algorithm returning a proper k-colouring of such a random graph G is known to exist when k < (1−ε ...
The χ-binding function of d-directional segment graphs
summary: To color a graph properly, one needs at least as many colors as the size of its biggest clique; therefore, the chromatic number χ is lower-bounded by the clique number ω. In general, there are no upper bounds on χ in terms of ω. The graphs for which we ...
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 ...