Seonghyuk Im

dblp:172/5830 · DBLP profile ↗
← Back
2ranked-venue papers
1as first author
2since 2021 · last 2025
0000-0003-1996-6801ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 1 first-author · 2 since 2021
YearPublicationVenuePosition
2025 The proper conflict-free k-coloring problem and the odd k-coloring problem are NP-complete on bipartite graphs
Jungho Ahn, Seonghyuk Im, Sang-il Oum
Discret. Appl. Math.2
2025 Dirac's Theorem for Linear Hypergraphs
abstract
Abstract. Dirac’s theorem states that any [Formula: see text]-vertex graph [Formula: see text] with even integer [Formula: see text] satisfying [Formula: see text] contains a perfect matching. We generalize this to [Formula: see text]-uniform linear hypergraphs by proving the following. Any [Formula: see text]-vertex [Formula: see text]-uniform linear hypergraph [Formula: see text] with minimum degree at least [Formula: see text] contains a matching that covers at least [Formula: see text] vertices. This minimum degree condition is asymptotically tight, and obtaining a perfect matching is impossible with any degree condition. Furthermore, we show that if [Formula: see text], then [Formula: see text] contains almost spanning linear cycles, almost spanning hypertrees with [Formula: see text] leaves, and “long subdivisions” of any [Formula: see text]-vertex graphs.
Seonghyuk Im, Hyunwoo Lee 0009
SIAM J. Discret. Math.1