9
$\begingroup$

I am looking for previous work regarding graphs whose vertices can be assigned colours (not necessarily a proper colouring) in such a way that each colour class induces a tree.

In particular I am most interested in results for planar graphs.

I have searched quite hard and there is a fairly extensive body of work on vertex-arboricity and linear vertex arboricity which relate to colouring a graph so that each colour class is a forest or a disjoint union of paths. (Rather than using the phrase "colouring the vertices", the vertex-arboricity etc is often defined as "partitioning the vertices" but of course they are the same thing.)

There are numerous extensions of the vertex-arboricity concept where the colour classes have to be nearly equal size, or when other restrictions are placed on the monochromatic subgraphs. In fact, put any of the words {equitable, list, star, critical, fractional} in front of "vertex-arboricity" and there is a paper on it.

The other relevant thing that came up was the phrase Yutsis graphs which refer to graphs that can be partitioned into two induced trees. However there are perhaps two or three papers on these, and they focussed primarily on cubic graphs, and did not help me.

So my question is:

Is there an accepted graph-theoretic term and/or associated literature related to the concept of partitioning the vertices of a graph into induced trees?

I am primarily concerned with exact structural results (things like characterisations of families of graphs that can be partitioned into very few trees) that I may be able to extend and/or adapt for my purposes.

I am not really interested in complexity results (e.g. NP-completeness) or anything to do with infinite graphs; there are numerous vertex-arboricity papers on complexity.

Improve this question
$\endgroup$
6
  • $\begingroup$ I’m confused. Isn’t every graph of this type? Or are you mostly interested in the least number of colors needed for such a decomposition? $\endgroup$
    – Pat Devlin
    Commented Aug 21, 2018 at 2:10
  • $\begingroup$ This looks helpful for you: faculty.math.illinois.edu/~west/openp/planforest.html $\endgroup$
    – Pat Devlin
    Commented Aug 21, 2018 at 2:20
  • $\begingroup$ @PatDevlin Thanks. Yes, I could always partition the vertices into $n$ one-vertex trees, so in that sense every graph is of that type. My primary concern is what can be said if, say, the number of allowed trees is just 2. $\endgroup$
    – Gordon Royle
    Commented Aug 21, 2018 at 3:32
  • $\begingroup$ If you can cut it into two induced trees, that’s a lot. What kind of information are you hoping for? $\endgroup$
    – Pat Devlin
    Commented Aug 21, 2018 at 3:37
  • 1
    $\begingroup$ @ViniciusdosSantos The vertices of planar graph can be partitioned in two trees if and only if its planar dual is hamiltonian. It is known that a hamiltonian planar triangulation has at least four hamilton cycles and I think that the result is true for other planar graphs (perhaps some connectivity or minimum degree constraint). The existing proof for triangulations fundamentally relies on it being a triangulation, so I wanted to change the domain and see if techniques from the "vertex arboricity" literature may help. But it must be trees. $\endgroup$
    – Gordon Royle
    Commented Sep 13, 2018 at 5:02

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .