Uniquely Partitionable Graphs
Béla Bollobás, Andrew G. Thomason · Journal of the London Mathematical Society · 1977
A graph is l-degenerate if it does not contain a subgraph whose minimum degree is greater than l.A (k,l)-partition of a graph G is a partition of the vertex set V(G) of G into k subsets V1,.., Vk, such that each Vl induces an l-degenerate graph. A graph with exactly one (k, l)-partition is said to be uniquely (k,l)-partitionable. Extending a number of earlier results, we prove that for every k, l and g there are non-trivial uniquely (k, l)-partitionable graphs of girth at least g.