A generalisation of matching and colouring Original Research Article

We define an r-bounded cover of a graph G to be a subgraph T⊆G such that T contains all vertices of G and each component of T is a complete subgraph of G of order at most r. A 2-bounded cover of a graph G corresponds to a matching of G, and an ω(G)-bounded cover of G corresponds to a colouring of the vertices of the complement Ḡ. We generalise a number of results on matching and colouring of graphs to r-bounded covers, including the Gallai–Edmonds Structure Theorem, Tutteʹs 1-Factor Theorem, and Gallaiʹs theorem on the minimal order of colour-critical graphs with connected complements.