기초과학연구원 이산수학그룹
Venue The K-Hotel Gyeongju Website https://indico.ibs.re.kr/e/kscw2025 Organizers Seokbeom Kim (김석범), KAIST and IBS Discrete Mathematics Group Hyunwoo Lee (이현우), KAIST and IBS Extremal Combinatorics and Probability Group Jaehyeon Seo (서재현), Yonsei University Kyungjin Cho (조경진), POSTECH
We prove that for any circle graph $H$ with at least one edge and for any positive integer $k$, there exists an integer $t=t(k,H)$ so that every graph $G$ either has a vertex-minor isomorphic to the disjoint union of $k$ copies of $H$, or has a $t$-perturbation with no vertex-minor isomorphic to $H$. Using the …
Lehel's conjecture states that every 2-edge-colouring of the complete graph $K_n$ admits a partition of its vertices into two monochromatic cycles. This was proven for sufficiently large n by Luczak, Rödl, and Szemerédi (1998), extended by Allen (2008), and fully resolved by Bessy and Thomassé in 2010. We consider a rainbow version of Lehel's conjecture …
We will discuss two symmetry breaking parameters: distinguishing number and fixing number. Despite being introduced independently, they share meaningful connections. In particular, we show that if a tree is 2-distinguishable with order at least 3, it suffices to fix at most 4/11 of the vertices and if a tree is $d$-distinguishable, $d \geq 3$, it …
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 …