4 papers
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…