4
$\begingroup$

It is known that every planar graph $G$ can be decomposed into at most 5 spanning star forests, which means that there exists at most five edge-disjoint spanning subgraphs of $G$ each of which is a forest with connected components being stars.

My question is as follows. Does there exist a constant $k$ such that every planar graph can be decomposed into at most $k$ spanning star forests such that every vertex of the graph is a center of at most one non-trivial (i.e., with at least 2 vertices) star in the decomposition?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

There is such a constant, namely $k=5$.

The proof that there is a decomposition into five star forests in [1] is based on an acyclic $5$-colouring of the vertex set. A vertex $v$ cannot be the centre of a non-trivial star in the forest $F_i$ unless it receives colour $i$ in the colouring. In particular, no vertex will be the centre of non-trivial stars in two different forests.

[1] Hakimi, S.L.; Mitchem, J.; Schmeichel, E., Star arboricity of graphs, Discrete Math. 149, 1996.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, Florian! Theorem 2 in the paper is exactly what I was looking for. $\endgroup$
    – Victor
    Commented Nov 27, 2017 at 9:11

You must log in to answer this question.

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