pith. sign in

arxiv: 1809.02799 · v1 · pith:UJPSJI45new · submitted 2018-09-08 · 🧮 math.CO · cs.DM

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
0
0 comments X
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.