Quasi-Bisections of Cubic Graphs with Tree and Circuit Decompositions
A $2$-quasi-bisection of a graph is a vertex $2$-coloring in which the color classes differ in size by at most two and every monochromatic component has at most two vertices. Esperet, Mazzuoccolo, and Tarsi in [J. Graph Theory, 86(2017), 149-158] conjectured that every cubic graph admits such a coloring. DeVos and Nurse proved the conjecture for cubic graphs whose edge sets can be partitioned into a tree and a circuit. This result is generalized in this paper for a larger family of cubic graphs. The conjecture is verified for cubic graphs whose edge set can be partitioned into two subsets $E(T)$ and $E(J)$, where $T$ is a tree of $G$ and $J$ is an even subgraph containing at most two odd circuit components.
Authors
- Rong‐Xia Hao (ORCID: https://orcid.org/0000-0001-8714-8750)
- Cun‐Quan Zhang (ORCID: https://orcid.org/0000-0001-5583-4481)
- Yilun Luo
- Xixiong Tang
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.48550/arxiv.2611.23885
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint