Skip to main content
2 of 3
added 645 characters in body
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. When it can, there is sometimes a name for a particular construction of this type. The circle method is one of several to construct a round robin tournament for $k+1$ players when $k$ is odd: A $k$ day tournament where each player plays one match each day and at the end all pairs have played. Consider the players as vertices of a complete graph $K_{k+1}$ and color the edges according to the day that pair plays their match. This decomposes the $\binom{k+1}2$ edges into $k$ perfect matchings.

Digression: 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 less obvious that, for $k$ odd, $K_{k+1}$ has property II. One way of proving this is the circle method mentioned above.

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 a name in general.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104