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?

$\endgroup$
0

1 Answer 1

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.