Stable-? ? partitions of graphs
For a set of graphs ? ? , the Stable-? ? problem asks whether, given a graph G G , we can find an independent set S S in G G , such that G?S?? G ? S ? ? . For instance, if ? ? is the set of all bipartite graphs, Stable-? ? coincides with vertex 3-colourability, and if ? ? is the set of 1-regular graphs, the problem is known as efficient edge domination. Numerous other examples of the Stable-? ? problem have been studied in the literature. In the present contribution, we systematically study the Stable-? ? problem with respect to the speed (a term meaning size) of ? ? . In particular, we show that for all hereditary classes ? ? with a subfactorial speed of growth, Stable-? ? is solvable in polynomial time. We then explore the problem for minimal hereditary factorial classes ? ? . Contrary to the conjecture proposed in Lozin (2005) [18], the complexity of Stable-? ? turns out to be polynomial for nearly all minimal hereditary factorial classes ? ? . On the other hand, if we do not require ? ? to be hereditary, the complexity of the problem can jump to NP-completeness.
stable-? ? partition ? ? ? ? ? hereditary property speed of graph property factorial property polynomial-time np-complete