4 papers · 1 filter
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 (and More)
Édouard Bonnet, Yeonsu Chang
We show that Max Independent Set (MIS) remains NP-hard in graphs excluding the grid as an induced minor. This negatively answers a question of Dallard--Milanič--Štorge…
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…