Skip to main content
1 of 3
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

Deciding if a given graph (or type of graph) can be constructed this way would seem the more likely question.

For example, There is much work on deciding if a graph $G$ is $k$-vertex colorable. Maximum degree $\lt k$ is certainly a sufficient condition. Here is a construction of such a graph: Start with $k$ disjoint vertex sets (some perhaps empty) and add some edges, but only between vertices in different sets. The result is certainly $k$-vertex-colorable and every such graph arises that way. But the construction does not have a name as far as I know.

Here are some more interesting properties for a regular graph. Consider a simple graph $G$ which is regular of degree $k.$ Then the vertex coloring number is at most $k+1$ and could be $2.$ The edge coloring number is at least $k.$ We might wonder if it has one or the other of these properties:

I) It can be vertex colored with $k+1$ colors so that each vertex has one neighbor of each color other than it's own.

II) It can be $k$-edge colored.

The complete graph $K_{k+1}$ somewhat trivially has property I.

It is kind of interesting that, for $k$ odd, $K_{k+1}$ has property II.

Another interesting result is that, for $k$ odd, property I implies property II: Given the coloring of $G$, color the vertices of $K_{k+1}$ with the same colors and consider a $k$-edge coloring of that complete graph as just mentioned. Now color each edge of (the vertex colored) $G$ with the same color as the correspondingly colored edge of the complete graph.

To get back to your question, it is immediate that property I precisely says that $G$ can be constructed in this way:

  • Consider $k+1$ disjoint vertex classes, each of the same size. Then choose $\binom{k+1}2$ matchings, one between each pair of classes.

While property II ($G$ is $k$-regular and $k$-edge colorable) precisely says that it arises from your construction:

  • Take $k$ edge disjoint perfect matchings ($1$-factors) on some $2m$ points. (I'm assuming simple graphs and $k>0$.)

But I don't know that either construction has aa name.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104