Gear Composition of Stable Set Polytopes and G-Perfection
研究了齿轮组合得到的图（齿轮图）的稳定集多面体，通过扩展原图的线性不等式描述其结构，并引入G-完美图类，证明反复应用齿轮组合得到的图是G-完美的，特别是一大类无爪图属于此类。
Graphs obtained by applying the gear composition to a given graph H are called geared graphs. We show how a linear description of the stable set polytope STAB(G) of a geared graph G can be obtained by extending the linear inequalities defining STAB(H) and STAB(H e ), where H e is the graph obtained from H by subdividing the edge e. We also introduce the class of 𝒢-perfect graphs, i.e., graphs whose stable set polytope is described by nonnegativity inequalities, rank inequalities, lifted 5-wheel inequalities, and some special inequalities called geared inequalities and g-lifted inequalities. We prove that graphs obtained by repeated applications of the gear composition to a given graph H are 𝒢-perfect, provided that any graph obtained from H by subdividing a subset of its simplicial edges is 𝒢-perfect. In particular, we show that a large subclass of claw-free graphs is 𝒢-perfect.