The extremal function of a graph is the supremum of densities of graphs not containing as a minor, where the density of a graph is the ratio of the number of edges to the number of vertices. Myers and Thomason (2005), Norin, Reed, Thomason and Wood (2020), and Thomason and Wales (2019) …
I am going to present an algorithm for computing a feedback vertex set of a unit disk graph of size k, if it exists, which runs in time , where and denote the numbers of vertices and edges, respectively. This improves the -time algorithm for this problem on unit disk …
Majority dynamics on a graph is a deterministic process such that every vertex updates its -assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, O'Donnell, Tamuz and Tan conjectured that, in the Erdős-Rényi random graph , the random initial -assignment converges to a -agreement with high …
Bouchet (1987) defined delta-matroids by relaxing the base exchange axiom of matroids. Oum (2009) introduced a graphic delta-matroid from a pair of a graph and its vertex subset. We define a -graphic delta-matroid for an abelian group , which generalizes a graphic delta-matroid. For an abelian group , a -labelled graph is a graph whose …
A family of subsets of {1,2,…,n} is called maximal k-wise intersecting if every collection of at most k members from has a common element, and moreover, no set can be added to while preserving this property. In 1974, Erdős and Kleitman asked for the smallest possible size of a …
