7 papers
QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
Édouard Bonnet, Yeonsu Chang
A hereditary graph class has strongly edge-sublinear separators if, for some constant , every graph in the class with edges admits a balanced separator of si…
Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor
Édouard Bonnet, Yeonsu Chang
We show that there is a fixed planar graph , namely the grid, such that Max Independent Set remains NP-hard in -induced-minor-free graphs. This refutes the Dalla…
Moderately beyond clique-width: reduced component max-leaf and related parameters
Édouard Bonnet, Yeonsu Chang, Julien Duron +2
Reduced parameters [BKW, JCTB '26; BKRT, SODA '22] are defined via contraction sequences. Based on this framework, we introduce the reduced component max-leaf, denoted by $\operato…
The optimal chromatic bound for even-hole-free graphs without induced seven-vertex paths
Shenwei Huang, Yidong Zhou, Yeonsu Chang
The class of even-hole-free graphs has been extensively studied on its own and on its relation to perfect graphs. In this paper, we study the -boundedness of even-hole-free grap…
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…