Edge Contraction and Forbidden Induced Graphs

Hany Ibrahim; Peter Tittmann

paper

Edge Contraction and Forbidden Induced Graphs

arXiv:2203.03491

Abstract

A graph $G$ is $H$ -free if any subset of $V (G)$ does not induce a subgraph of $G$ that is isomorphic to $H$ . Given a graph $H$ , we present sufficient and necessary conditions for a graph $G$ such that $G / e$ is $H$ -free for any edge $e$ in $E (G)$ . Thereafter, we use these conditions to characterize forests, claw-free, $2 K_{2}$ -free, $C_{4}$ -free, $C_{5}$ -free, split, and pseudo-split graphs.