기초과학연구원 이산수학그룹
Recently, Letzter proved that any graph of order n contains a collection P of $O(n \log^*n)$ paths with the following property: for all distinct edges e and f there exists …
Tree decompositions are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition …
We study the fundamental problem of finding small dense subgraphs in a given graph. For a real number $s>2$, we prove that every graph on $n$ vertices with average degree …
We define new graph parameters, called flip-width, that generalize treewidth, degeneracy, and generalized coloring numbers for sparse graphs, and clique-width and twin-width for dense graphs. The flip-width parameters are defined …
The Erdős-Sós conjecture states that the maximum number of edges in an $n$-vertex graph without a given $k$-vertex tree is at most $\frac {n(k-2)}{2}$. Despite significant interest, the conjecture remains …
A graph class $\mathcal{G}$ has the strong Erdős-Hajnal property (SEH-property) if there is a constant $c=c(\mathcal{G}) > 0$ such that for every member $G$ of $\mathcal{G}$, either $G$ or its …
An archetype problem in extremal combinatorics is to study the structure of subgraphs appearing in different classes of (hyper)graphs. We will focus on such embedding problems in uniformly dense hypergraphs. …
Consider the following hat guessing game: $n$ players are placed on $n$ vertices of a graph, each wearing a hat whose color is arbitrarily chosen from a set of $q$ …
A theoretical dynamical system is a pair (X,T) where X is a compact metric space and T is a self homeomorphism of X. The topological entropy of a theoretical dynamical system …
The well-known 1-2-3 Conjecture by Karoński, Łuczak and Thomason states that the edges of any connected graph with at least three vertices can be assigned weights 1, 2 or 3 …