I spent a lot of time this intersession trying to prove the following statement:
The edge set of a graph $G$ with maximum degree $\Delta$ can be decomposed into $\lceil {\Delta \over 2} \rceil$ disjoint classes such that each vertex in $G$ is incident to at most 2 edges in any class.
I had mainly been thinking about constructing an algorithm that would construct one class per iteration, but I couldn't prove any algorithm I could come up with would terminate in $\lceil {\Delta \over 2} \rceil$ steps.
I was also reviewing a paper over the break, and one of the references looked interesting with respect to this problem I had been working on. I followed the breadcrumbs are found the linear arboricity conjecture, first raised by Akiyama, Exoo, and Harary in 1981:
I was also reviewing a paper over the break, and one of the references looked interesting with respect to this problem I had been working on. I followed the breadcrumbs are found the linear arboricity conjecture, first raised by Akiyama, Exoo, and Harary in 1981:
A linear forest is a forest in which every tree is a path. The linear arboricity $la(G)$ of a graph $G$ is the minimum number of linear forests whose union is the edge set of $G$. The linear arboricity conjecture asserts that for every simple graph $G$ with maximum degree $\Delta$, we have $la(G) \leq \left[ {\Delta + 1 \over 2} \right]$.
(I'm using Alon's definition here.) This is really similar to the problem I'd been working on, the key difference being that my version allowed for cycles while linear arboricity does not.
The conjecture holds for small $\Delta$, namely $\Delta \leq 6$ and $\Delta = 8, 10$. There are also some probabilistic results. In 1988, Alon showed that one needs at most ${\Delta \over 2} + c \Delta^{3/4} \log(\Delta)^{1/2}$ linear forests in the edge decomposition. And in 1994, McDiarmid and Reed verified the conjecture for almost all graphs.
It's amazing how much time I spent working on a problem that's probably too tough for me to take down in a couple of weeks just because I didn't know what to call the thing I was looking for. But the process, like always, was fun. I just think we'll have to settle for some more piecemeal results in our paper.
The conjecture holds for small $\Delta$, namely $\Delta \leq 6$ and $\Delta = 8, 10$. There are also some probabilistic results. In 1988, Alon showed that one needs at most ${\Delta \over 2} + c \Delta^{3/4} \log(\Delta)^{1/2}$ linear forests in the edge decomposition. And in 1994, McDiarmid and Reed verified the conjecture for almost all graphs.
It's amazing how much time I spent working on a problem that's probably too tough for me to take down in a couple of weeks just because I didn't know what to call the thing I was looking for. But the process, like always, was fun. I just think we'll have to settle for some more piecemeal results in our paper.
RSS Feed
