5 papers
Every tournament of dichromatic number has a vertex whose out-neighborhood has dichromatic number more than
Seokbeom Kim, Sang-il Oum
The dichromatic number of a tournament is the minimum number of colors needed to color the vertices so that no directed cycle is monochromatic. Nguyen, Scott, and Seymour (2025) as…
An FPT algorithm for cycle rank on semi-complete digraphs
Seokbeom Kim, O-joung Kwon, Myounghwan Lee
Cycle rank is a depth parameter for digraphs introduced by Eggan in 1963. Gruber (DMTCS 2012) and Giannopoulou, Hunter, and Thilikos (DAM 2012) asked whether the problem of determi…
On the chromatic number of the union of comparability graphs
Wouter Cames van Batenburg, Maria Chudnovsky, Linda Cook +3
Resolving in a strong sense a problem of Gyárfás on the union of two perfect graphs, we prove that for every pair of positive integers and , there is a graph with clique…
On a weaker notion of cross -intersecting families
Jiangdong Ai, Ming Chen, Seokbeom Kim +1
We prove that if two families and satisfy $\sum_{1 \leq i, j \leq \ell} \lvert F_i \cap F_j' \rvert…
An efficient algorithm for -subgraph-free Edge Deletion on graphs having a product structure
Shinwoo An, Seonghyuk Im, Seokbeom Kim +1
Given a family of graphs, a graph is \emph{-subgraph-free} if it has no subgraph isomorphic to a member of . We present a fixed-parameter li…