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$
  • $\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 '13 at 15:58
  • 1
    $\begingroup$ @NickGill, doesn't it only say that when $n$ is even? Consider $n = 3$. $\endgroup$ – Tom Leinster Nov 12 '13 at 17:50
  • $\begingroup$ @Tom, you're quite right. I forgot to specify that $n$ was even. $\endgroup$ – Nick Gill Nov 13 '13 at 9:39
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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry, I was so caught up in my construction interpretation I didn't realize I was literally defining edge coloring. $\endgroup$ – edgecoloring Nov 15 '13 at 8:42
3
$\begingroup$

That's called Vizing's theorem.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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