3
$\begingroup$

Given a graph $G$, it is possible to construct a sequence $H_1, H_2, \dotsc, H_k$ of graphs each a set of disjoint edges (i.e., every vertex of degree at most $1$) with $G = \bigcup H_i$.

For example:

For the complete bipartite graph $K_{n,n}$, only $n$ graphs are needed, which can be seen by taking one perfect matching, and then fixing one set and cyclically rotating the edges on the other.

For $K_2$, obviously $1$ graph is needed, for $K_3$, we have $n = 3$ since each edge must be added separately, and for $K_4$, we have again $n = 3$ (opposite edges, opposite edges, diagonals).


For any graph $G$, is there a way to calculate the minimal number $k$ of graphs $H_k$ needed to construct $G$, and furthermore a way to explicitly specify each $H_i$?

$\endgroup$
3
  • $\begingroup$ Theorem 4.4 of orion.math.iastate.edu/burstein/2003/math314/gt2003decomp.pdf asserts that $K_n$ is decomposable using $n-1$ subgraphs. $\endgroup$
    – Nick Gill
    Nov 12, 2013 at 15:58
  • 1
    $\begingroup$ @NickGill, doesn't it only say that when $n$ is even? Consider $n = 3$. $\endgroup$ Nov 12, 2013 at 17:50
  • $\begingroup$ @Tom, you're quite right. I forgot to specify that $n$ was even. $\endgroup$
    – Nick Gill
    Nov 13, 2013 at 9:39

2 Answers 2

5
$\begingroup$

Well, in some sense, there is no known way of doing it effectively for arbitrary graphs. (It is NP complete to determine whether $k=\Delta(G)$ or $k=\Delta(G)+1$.) You are actually interested in the edge chromatic number of a graph. See:

http://en.wikipedia.org/wiki/Edge_coloring

$\endgroup$
1
  • $\begingroup$ Sorry, I was so caught up in my construction interpretation I didn't realize I was literally defining edge coloring. $\endgroup$ Nov 15, 2013 at 8:42
3
$\begingroup$

That's called Vizing's theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.