Concept
Coloration des arêtes d'un graphe
Publications associées (169)
Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
Mikhail Kapralov, Slobodan Mitrovic, Ashkan Norouzi Fard, Jakab Tardos
Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a sm ...
ASSOC COMPUTING MACHINERY2020Edge colorings of graphs without monochromatic stars
In this note, we improve on results of Hoppen, Kohayakawa and Lefmann about the maximum number of edge colorings without monochromatic copies of a star of a fixed size that a graph on n vertices may admit. Our results rely on an improved application of an ...
ELSEVIER2020Minimum-Error Classes for Matching Parts
This paper examines the binning of two types of parts with random characteristics, so that a componentwise monotonic evaluation criterion exhibits a minimum deviation to a given target value over all possible realizations. The optimal matching classes are ...
2020Ramsey numbers of ordered graphs
An ordered graph is a pair G = (G,
ELECTRONIC JOURNAL OF COMBINATORICS2020Fast and Accurate Efficient Streaming Subgraph Isomorphism
Karl Aberer, Quoc Viet Hung Nguyen, Chi Thang Duong, Trung-Dung Hoang
Queries to detect isomorphic subgraphs are important in graph-based data management. While the problem of subgraph isomorphism search has received considerable attention for the static setting of a single query, or a batch thereof, existing approaches do n ...
2020Minimal graphs for 2-factor extension
Let G = (V, E) be a simple loopless finite undirected graph. We say that G is (2-factor) expandable if for any non-edge uv, G + uv has a 2-factor F that contains uv. We are interested in the following: Given a positive integer n = vertical bar V vertical b ...
ELSEVIER2020Tight Bounds for Online Edge Coloring
Vizing's celebrated theorem asserts that any graph of maximum degree Delta admits an edge coloring using at most Delta + 1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2 Delt ...
IEEE COMPUTER SOC2019On the Rainbow Turan number of paths
Let F be a fixed graph. The rainbow Turan number of F is defined as the maximum number of edges in a graph on n vertices that has a proper edge-coloring with no rainbow copy of F (i.e., a copy of F all of whose edges have different colours). The systematic ...
ELECTRONIC JOURNAL OF COMBINATORICS2019Distributed Coloring of Graphs with an Optimal Number of Colors
This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e. with the minimum number of colors) in the LOCAL model of computation. Most of the work on distributed vertex coloring so far has focused on ...
SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS2019Thrackles: An improved upper bound
A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, ex ...
ELSEVIER SCIENCE BV2019