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) …
The Alon-Jaeger-Tarsi conjecture states that for any finite field of size at least 4 and any nonsingular matrix over there exists a vector such that neither nor has a 0 component. In joint work with János Nagy we proved this conjecture when the size of the field is sufficiently …
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 …
The Gyárfás-Sumner conjecture says that for every forest , there is a function such that the chromatic number is at most for every -free graph ("-free" means with no induced subgraph isomorphic to , and is the size of the largest clique of ). This well-known conjecture has been proved only for a …
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 …
The independence number of a tree decomposition of a graph is the smallest integer such that each bag of induces a subgraph with independence number at most . If a graph is given together with a tree decomposition with bounded independence number, then the Maximum Weight Independent Set (MWIS) problem can …
