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$?

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

2 Answers 2

Reset to default
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

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

That's called Vizing's theorem.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .