Nathan Karst
  • Home
  • Teaching
  • Research

Linear arboricity

1/22/2013

0 Comments

 
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:
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. 
0 Comments



Leave a Reply.

    Archives

    June 2015
    May 2015
    February 2015
    December 2014
    October 2014
    September 2014
    August 2014
    July 2014
    May 2014
    March 2014
    February 2014
    January 2014
    December 2013
    October 2013
    July 2013
    June 2013
    May 2013
    April 2013
    March 2013
    February 2013
    January 2013

    Nathan Karst

    Doing and teaching mathematics. 

    Categories

    All

    RSS Feed

Powered by Create your own unique website with customizable templates.
Photo from ByoLogyc