2023/12/01 by Romaniello, Federico
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2312.00418
A k-bisection of a multigraph G is a partition of its vertex set into two parts of the same cardinality such that every component of each part has at most k vertices. Cui and Liu shown that every claw-free cubic multigraph contains a 2-bisection, while Eom and Ozeki constructed specific 2-bisections with bounded number of monochromatic edges. Their bound is the best possible for claw-free cubic simple graphs. In this note, we extend the latter result to the larger family of claw-free cubic multigraphs