Tag: graphs
Eliminating more than vertices in graphs
summary: Considérons le jeu suivant sur un graphe. À chaque tour, le joueur peut enlever un sommet de chaque composante connexe du graphe courant. Le but du jeu est d’éliminer tous les sommets du graphe. Le nombre minimum de tours nécessaires est appelé la treedepth du graphe. C’est ...
Reconstruction de graphes via des requêtes sur les triplets
summary: Considérons un oracle disposant d'un graphe labellisé caché. L'objectif de la reconstruction de graphes est de retrouver ce graphe caché en interrogeant l'oracle avec certains types de requêtes. Les requêtes que nous examinons portent sur des triplets de sommets du graphe, plus précisément, sur la structure ...
Fractional domatic number and minimum degree
summary: We present a study of a graph parameter in graph theory, named the fractional domatic number. A dominating set in a graph is a set of vertices such that every vertex outside the set is adjacent to a vertex in the set. The domatic number of a graph is ...
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−ε ...
Page 1 / 4 »