A note on the edge partition of graphs containing either a light edge or an alternating 2-cycle
classification
🧮 math.CO
cs.DM
keywords
alphamathcaldeltaedgeeverygraphalternatingcycle
read the original abstract
Let $\mathcal{G}_{\alpha}$ be a hereditary graph class (i.e, every subgraph of $G_{\alpha}\in \mathcal{G}_{\alpha}$ belongs to $\mathcal{G}_{\alpha}$) such that every graph $G_{\alpha}$ in $\mathcal{G}_{\alpha}$ has minimum degree at most 1, or contains either an edge $uv$ such that $d_{G_{\alpha}}(u)+d_{G_{\alpha}}(v)\leq \alpha$ or a 2-alternating cycle. It is proved that every graph in $\mathcal{G}_{\alpha}$ ($\alpha\geq 5$) with maximum degree $\Delta$ can be edge-partitioned into two forests $F_1$, $F_2$ and a subgraph $H$ such that $\Delta(F_i)\leq \max\{2,\lceil\frac{\Delta-\alpha+6}{2}\rceil\}$ for $i=1,2$ and $\Delta(H)\leq \alpha-5$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.