Strongly maximal H-free spanning subgraph

From Egres Open
Jump to: navigation, search

Let the graphs [math]G=(V,E) [/math] and [math]H [/math] be fixed. An edge set [math]F\subseteq E [/math] is called [math] H [/math]-free if [math](V,F) [/math] does not contain [math]H [/math] as a subgraph. We say that [math]F [/math] is strongly maximal if for any [math]H [/math]-free edge set [math]I\subseteq E [/math] we have [math]\left|I \setminus F\right| \leq \left|F \setminus I\right| [/math].

If [math]H[/math] is the path of length two, then we talk about strongly maximal matchings, and any [math]G [/math] admits such a matching ([1] p. 16. Theorem 5.6). For what other graphs [math]H [/math] can we guarantee the existence of a strongly maximal [math]H [/math]-free [math]F [/math] for any [math]G [/math]?


  1. R. Diestel and C.St.J.A. Nash-Williams, Directions in infinite graph theory and combinatorics, North-Holland, 1992. author link