4 papers
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
Maria Chudnovsky, Wouter Cames van Batenburg, 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 cliq…
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…