Zobrazeno 1 - 10
of 291
pro vyhledávání: '"Oum Sang-il"'
Autor:
Gollin, J. Pascal, Hendrey, Kevin, Huang, Hao, Huynh, Tony, Mohar, Bojan, Oum, Sang-il, Yang, Ningyuan, Yu, Wei-Hsuan, Zhu, Xuding
Motivated by the analysis of consensus formation in the Deffuant model for social interaction, we consider the following procedure on a graph $G$. Initially, there is one unit of tea at a fixed vertex $r \in V(G)$, and all other vertices have no tea.
Externí odkaz:
http://arxiv.org/abs/2405.15353
One of the fundamental results in graph minor theory is that for every planar graph $H$, there is a minimum integer $f(H)$ such that graphs with no minor isomorphic to $H$ have treewidth at most $f(H)$. A lower bound for ${f(H)}$ can be obtained by c
Externí odkaz:
http://arxiv.org/abs/2402.17255
Autor:
Dabrowski, Konrad K., Dross, François, Jeong, Jisu, Kanté, Mamadou Moustapha, Kwon, O-joung, Oum, Sang-il, Paulusma, Daniël
A graph $G$ contains a graph $H$ as a pivot-minor if $H$ can be obtained from $G$ by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in the study of rank-width. Pivot-minors have mainly been studied from a
Externí odkaz:
http://arxiv.org/abs/2311.04656
A class $\mathcal F$ of graphs is $\chi$-bounded if there is a function $f$ such that $\chi(H)\le f(\omega(H))$ for all induced subgraphs $H$ of a graph in $\mathcal F$. If $f$ can be chosen to be a polynomial, we say that $\mathcal F$ is polynomiall
Externí odkaz:
http://arxiv.org/abs/2310.11167
The clustered chromatic number of a graph class $\mathcal{G}$ is the minimum integer $c$ such that every graph $G\in\mathcal{G}$ has a $c$-colouring where each monochromatic component in $G$ has bounded size. We study the clustered chromatic number o
Externí odkaz:
http://arxiv.org/abs/2308.15721
Autor:
Kim, Donggyu, Oum, Sang-il
We show that the basis graph of an even delta-matroid is Hamiltonian if it has more than two vertices. More strongly, we prove that for two distinct edges $e$ and $f$ sharing a common end, it has a Hamiltonian cycle using $e$ and avoiding $f$ unless
Externí odkaz:
http://arxiv.org/abs/2308.05772
Autor:
Bergougnoux, Benjamin, Chekan, Vera, Ganian, Robert, Kanté, Mamadou Moustapha, Mnich, Matthias, Oum, Sang-il, Pilipczuk, Michał, van Leeuwen, Erik Jan
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space
Externí odkaz:
http://arxiv.org/abs/2307.01285
For each $d\leq3$, we construct a finite set $F_d$ of multigraphs such that for each graph $H$ of girth at least $5$ obtained from a multigraph $G$ by subdividing each edge at least two times, $H$ has twin-width at most $d$ if and only if $G$ has no
Externí odkaz:
http://arxiv.org/abs/2306.05334
Publikováno v:
Random Structures Algorithms, 65(4):794-831, December 2024
We investigate the twin-width of the Erd\H{o}s-R\'enyi random graph $G(n,p)$. We unveil a surprising behavior of this parameter by showing the existence of a constant $p^*\approx 0.4$ such that with high probability, when $p^*\le p\le 1-p^*$, the twi
Externí odkaz:
http://arxiv.org/abs/2212.07880
In 1965, Erd\H{o}s and P\'{o}sa proved that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold for odd cycles, and Dejter and Neumann-Lara asked in
Externí odkaz:
http://arxiv.org/abs/2209.09488