기초과학연구원 이산수학그룹
We prove that for all positive integers $k$ and $d$, the class of $K_{1,d}$-free graphs not containing the $k$-ladder or the $k$-wheel as an induced minor has a bounded tree-independence number. Our proof uses a generalization of the concept of brambles to tree-independence number. This is based on joint work with Claire Hilaire, Martin Milanič, …
Nowhere-zero flows of unsigned graphs were introduced by Tutte in 1954 as a dual problem to vertex-coloring of (unsigned) planar graphs. The definition of nowhere-zero flows on signed graphs naturally comes from the study of embeddings of graphs in non-orientable surfaces, where nowhere-zero flows emerge as the dual notion to local tensions. Nowhere-zero flows in …
Given a $k$-uniform hypergraph $H$, the Ramsey number $R(H;q)$ is the smallest integer $N$ such that any $q$-coloring of the edges of the complete $k$-uniform hypergraph on $N$ vertices contains a monochromatic copy of $H$. When $H$ is a complete hypergraph, a classical argument of Erdős, Hajnal, and Rado reduces the general problem to the …
A graph $G$ is (list, DP) $k$-critical if the (list, DP) chromatic number is $k$ but for every proper subgraph $G'$ of $G$, the (list, DP) chromatic number of $G'$ is less than $k$. For $k\geq 4$, we show a bound on the minimum number of edges in a DP $k$-critical graph, and our bound …
Robertson and Seymour introduced branch-width as a connectivity invariant of graphs in their proof of the Wagner conjecture. Decompositions based on this invariant provide a natural framework for implementing dynamic-programming algorithms to solve graph optimization problems. We will discuss the computational issues involved in using branch-width as as a general tool in discrete optimization.
Vertex Cover is perhaps the most-studied problem in parameterized complexity that frequently serves as a testing ground for new concepts and techniques. In this talk, I will focus on a generalization of Vertex Cover called Component Order Connectivity (COC). Given a graph G, an integer k and a positive integer d, the task is to …
We consider a continuous model of graphs, introduced by Dearing and Francis in 1974, where each edge of G to be a unit interval, giving rise to an infinite metric space that contains not only the vertices of G but all points on all edges of G. Several standard graph problems can be defined and …
Given a $k$-uniform hypergraph $F$, its Turán density $\pi(F)$ is the infimum over all $d\in $ such that any $n$-vertex $k$-uniform hypergraph $H$ with at least $d\binom{n}{k}+o(n^k)$ edges contains a copy of $F$. While Turán densities are generally well understood for graphs ($k=2$), the problem becomes notoriously difficult for $k\geq 3$, even for small hypergraphs. …
Consider a general Turan-type problem on hypergraphs. Let $\mathcal{F}$ be a family of $k$-subsets of $$ that does not contain sets $F_1, \ldots, F_s$ satisfying some property $P$. We show that if $P$ is low-dimensional in some sense (e.g., is defined by intersections of bounded size) then, under polynomial dependencies between $n, k$ and the …
Let $F_{k,d}(n)$ be the maximal size of a set ${A}\subseteq $ such that the equation \ has no solution with $a_1,a_2,\ldots,a_k\in A$ and integer $x$. Erdős, Sárközy and T. Sós studied $F_{k,2}$, and gave bounds when $k=2,3,4,6$ and also in the general case. We study the problem for $d=3$, and provide bounds for $k=2,3,4,6$ and …