Sang-il Oum (엄상일), The Erdős-Pósa property for circle graphs as vertex-minors
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 …
10 events found.
Events
-
-
Room B332 IBS (기초과학연구원)
-
-
Zhifei Yan, A Rainbow version of Lehel’s conjecture
Room B332 IBS (기초과학연구원)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, …
-
Katherine Perry, Symmetry breaking in trees
Room B332 IBS (기초과학연구원)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 …
-
Mujin Choi (최무진), Excluding ladder and wheel as induced minor in graphs without induced stars
Room B332 IBS (기초과학연구원)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 …
-
Rong Luo, Modulo flows and Integer flows of signed graphs
Room B332 IBS (기초과학연구원)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 …
-
Marcelo Sales, On the Ramsey number of Daisies and other hypergraphs
Room B332 IBS (기초과학연구원)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 …
-
-
Ilkyoo Choi (최일규), An improved lower bound on the number of edges in list critical graphs via DP coloring
Room B332 IBS (기초과학연구원)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'$ …
-
William Cook, Optimization via Branch Decomposition
Room B332 IBS (기초과학연구원)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 …
-
Jakob Greilhuber, A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
Room B332 IBS (기초과학연구원)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 …
-
-
Ahmed Ghazy and Tim Hartmann, Continuous Graphs – An Overview and a Coloring Problem
Room B332 IBS (기초과학연구원)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 …