Tag: graphs
Recent Advances in Distributed Coloring
summary: The study of distributed graph algorithms aims to understand the limitations inherent to local computations. In a seminal paper, Linial (1992, SIAM J. Computing) introduced the LOCAL model to formalize this question. In this model, the input graph is seen as a communication network where vertices are computers. They ...
An acylic orientation problem with parity constraints
summary: Let G = (V, E) be a connected graph and T be a subset of the vertices. An orientation of G is a choice of a direction for each edge of the graph, it is said to be acylic if does not contain any directed cycle. An orientation of G ...
Transversals in a collection of graphs with degree conditions
summary: Let G={G_1, G_2, ... , G_m} be a collection of n-vertex graphs on the same vertex set V (a graph system), and F be a simple graph with e(F) ≤ m. If there is an injection f: E(F) → [m] such that e &isinv E(G_{f(e)}) for each ...
Compact local certification of MSO properties for several tree-like parameters
summary: Local certification is interested in assigning labels (called certificates) to the vertices of a graph, in order to certify a certain property about said graph, or the correctness of a data-structure distributed on the graph. For the verification to be local, a vertex may only "see" its neighbourhood. A ...
Complexité du problème de distance d’édition minimum à un line-digraphe
summary: La distance d'édition est une mesure classique utilisée pour évaluer la proximité entre un graphe donné et un autre graphe ou une classe de graphes. Cette distance représente le nombre minimum de modifications requises pour transformer le graphe initial en un graphe appartenant à la classe voulue. Une ...
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 ...