Edge Contraction and Line Graphs

Hany Ibrahim, Peter Tittmann

Published 2022-12-17Version 1

Given a family of graphs $\mathcal{H}$, a graph $G$ is $\mathcal{H}$-free if any subset of $V(G)$ does not induce a subgraph of $G$ that is isomorphic to any graph in $\mathcal{H}$. We present sufficient and necessary conditions for a graph $G$ such that $G/e$ is $\mathcal{H}$-free for any edge $e$ in $E(G)$. Thereafter, we use these conditions to characterize claw-free, matrogenic and line graphs.