betaFeedback

WorksMathematics

Quasi-Bisections of Cubic Graphs with Tree and Circuit Decompositions

Abstract

A 22-quasi-bisection of a graph is a vertex 22-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)E(T) and E(J)E(J), where TT is a tree of GG and JJ is an even subgraph containing at most two odd circuit components.

Paper details

vlnc:W_gv24han9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…