6 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…
Unavoidable butterfly minors in digraphs of large cycle rank
Meike Hatzel, O-joung Kwon, Myounghwan Lee +1
Cycle rank is one of the depth parameters for digraphs introduced by Eggan in 1963. We show that there exists a function such that every digraph of cyc…
Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
Shinwoo An, Yeonsu Chang, Kyungjin Cho +4
Horiyama et al. (AAAI 2024) considered the problem of generating instances with a unique minimum vertex cover under certain conditions. The Minimum Pre-assignment for Uniquificatio…
A characterization of graphs of radius- flip-width at most
Yeonsu Chang, Sejin Ko, O-joung Kwon +1
The -flip-width of a graph, for , is a graph parameter defined in terms of a variant of the cops and robber game, called the flipper game, and it…
A new width parameter of graphs based on edge cuts: -edge-crossing width
Yeonsu Chang, O-joung Kwon, Myounghwan Lee
We introduce graph width parameters, called -edge-crossing width and edge-crossing width. These are defined in terms of the number of edges crossing a bag of a tree-cut decompos…
Graphs without two vertex-disjoint -cycles
Minjeong Kang, O-joung Kwon, Myounghwan Lee
Lovász (1965) characterized graphs without two vertex-disjoint cycles, which implies that such graphs have at most three vertices hitting all cycles. In this paper, we ask whether…