The vertex set of any simple graph admits an equitable partition into k induced linear forests for every k at least max of ceil((Δ(G)+1)/2) and ceil(|G|/4).
Equitable partition of plane graphs with independent crossings into induced forests
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
The cluster of a crossing in a graph drawing in the plane is the set of the four end-vertices of its two crossed edges. Two crossings are independent if their clusters do not intersect. In this paper, we prove that every plane graph with independent crossings has an equitable partition into $m$ induced forests for any $m\geq 8$. Moreover, we decrease this lower bound 8 for $m$ to 6, 5, 4 and 3 if we additionally assume that the girth of the considering graph is at least 4, 5, 6 and 26, respectively.
fields
math.CO 1years
2019 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Equitable partition of graphs into induced linear forests
The vertex set of any simple graph admits an equitable partition into k induced linear forests for every k at least max of ceil((Δ(G)+1)/2) and ceil(|G|/4).