PreprintCC BY 4.0arXiv
Decomposing multigraphs into two Class I subgraphs with prescribed maximum degrees
Abstract
Let G be a finite loopless multigraph with maximum degree Δ and χ'(G)=Δ+k, where k≥0. We prove that for every pair of positive integers p,q satisfying p+q=Δ+k and p,q≤Δ, the graph G admits an edge decomposition into two spanning Class I subgraphs Hp,Hq with Δ(Hp)=p and Δ(Hq)=q.
Related
- Central Limit Theorem of Maximum Weight Matching on Random Graphs with Prescribed Degrees
- Large induced subgraphs with k vertices of maximum degree
- On the Minimum Possible Maximum Degree of Induced Subgraphs of Product Graphs
- Maximum spread of vertex degrees in a simple graph
- Short Paper No. 1: Relation between integer sequence A319433 and the maximum degrees of finite linear Jaco graphs
BibTeX
@misc{chen2026decomposing,
title = {{Decomposing multigraphs into two Class I subgraphs with prescribed maximum degrees}},
author = {Yonglei Chen and Yan Cao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21097},
eprint = {2610.21097},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21097},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Decomposing multigraphs into two Class I subgraphs with prescribed maximum degrees
AU - Yonglei Chen
AU - Yan Cao
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.21097
UR - https://arxiv.org/abs/2610.21097
AB - Let G be a finite loopless multigraph with maximum degree Δ and χ'(G)=Δ+k, where k≥0. We prove that for every pair of positive integers p,q satisfying p+q=Δ+k and p,q≤Δ, the graph G admits an edge decomposition into two spanning Class I subgraphs H_p,H_q with Δ(H_p)=p and Δ(H_q)=q.
ER -